计算Delaunay三角网，通过调整阈值，得到不同的外接多边形（凸、非凸）
这里的凸的意思是外接凸多边形，非凸指的是按照最外面的点相互连接得到的多边形。如这里白色区域为非凸，外面绿色连线围成的区域为凸。
以下代码生成的为非凸。
points = [(319, 320), (125, 198), (250, 366), (129, 182), (262, 375), (235, 344), (248, 369), (367, 261), (196, 307), (163, 286)]pts = np.array(pts).astype(np.int32)
points = ptsfrom scipy.spatial import Delaunaydef alpha_shape(points, alpha, only_outer=True):"""Compute the alpha shape (concave hull) of a set of points.:param points: np.array of shape (n,2) points.:param alpha: alpha value.:param only_outer: boolean value to specify if we keep only the outer borderor also inner edges.:return: set of (i,j) pairs representing edges of the alpha-shape. (i,j) arethe indices in the points array."""assert points.shape[0] > 3, "Need at least four points"def add_edge(edges, i, j):"""Add an edge between the i-th and j-th points,if not in the list already"""if (i, j) in edges or (j, i) in edges:# already addedassert (j, i) in edges, "Can't go twice over same directed edge right?"if only_outer:# if both neighboring triangles are in shape, it's not a boundary edgeedges.remove((j, i))returnedges.add((i, j))tri = Delaunay(points)edges = set()# Loop over triangles:# ia, ib, ic = indices of corner points of the trianglefor ia, ib, ic in tri.vertices:pa = points[ia]pb = points[ib]pc = points[ic]# Computing radius of triangle circumcircle# www.mathalino.com/reviewer/derivation-of-formulas/derivation-of-formula-for-radius-of-circumcirclea = np.sqrt((pa[0] - pb[0]) ** 2 + (pa[1] - pb[1]) ** 2)b = np.sqrt((pb[0] - pc[0]) ** 2 + (pb[1] - pc[1]) ** 2)c = np.sqrt((pc[0] - pa[0]) ** 2 + (pc[1] - pa[1]) ** 2)s = (a + b + c) / 2.0area = np.sqrt(s * (s - a) * (s - b) * (s - c))circum_r = a * b * c / (4.0 * area)print('circum_r', circum_r)if circum_r < alpha:add_edge(edges, ia, ib)add_edge(edges, ib, ic)add_edge(edges, ic, ia)return edges# Computing the alpha shape
# 通过这里的alpha阈值，可以得到不同的外接多边形。阈值选的不好，可能得不到外接多边形。比如选的太小。
edges = alpha_shape(points, alpha=200, only_outer=True)
print('edges', edges)# Plotting the output
fig, ax = plt.subplots(figsize=(6,4))
ax.axis('equal')
plt.plot(points[:, 0], points[:, 1], '.',color='b')
for i, j in edges:# print(points[[i, j], 0], points[[i, j], 1])ax.plot(points[[i, j], 0], points[[i, j], 1], color='red')pass
ax.invert_yaxis()
plt.show()