如何确定一个点是否位于凹壳内(阿尔法形状)？

Question

我在二维平面上有一组坐标，我希望从它构造一个凹的船体(阿尔法形状)。在此之后，我需要确定某个点是在形成的船体内部还是外部。

虽然我可以使用附加的代码来实现凸壳，但我还没有找到一种方法来实现凹壳。

# Detection in Convex Hulls
from scipy.spatial import Delaunay

hull = Delaunay(points)
return hull.find_simplex(test_point) >= 0

我怎样才能达到同样的凹壳？

Answer 1

使用阿尔法形状包。下面是一个示例代码：

import matplotlib.pyplot as plt
from descartes import PolygonPatch
import alphashape
import random
from shapely.geometry import Point

points = [(0., 0.), (0., 1.), (1., 1.), (1., 0.),
          (0.5, 0.25), (0.5, 0.75), (0.25, 0.5), (0.75, 0.5)]

alpha_shape = alphashape.alphashape(points, 2.0) # Create the alpha shape

# Plotting the alpha shape over the input data
fig, ax = plt.subplots()
ax.scatter(*zip(*points), c='green')
ax.add_patch(PolygonPatch(alpha_shape, alpha=0.2))

N = 10 # number of random points
for i in range(N):
    x = round(random.uniform(0, 1), 2)
    y = round(random.uniform(0, 1), 2)
    point = Point(x,y) # analysis point
    if alpha_shape.contains(point) == True:
        plt.scatter(x,y,c='blue')
    else:
        plt.scatter(x,y,c='red')

​

​

图例：

1. (红色)，凹多边形(
2. )外点(绿色)，顶点点(
3. )蓝色，凹多边形(

)内点。

Answer 2

Shapely包含point.within(多边形)和polygon.contains(点)方法。