无法在Python中使用scipy在凹多边形内部生成正确的三角形网格

Question

我在工作中遇到一个任务，需要使用Python在几个不同的多边形内部创建三角形网格。虽然多边形是凸面外壳的分段，但每个分段本身都是凹面形状。当我尝试使用scipy.spatial.Delaunay（）时，该算法似乎假设多边形为凸多边形，并最终在凹壳区域外生成三角形。代码和结果图如下所示

for i in range(len(mp)):
    dtri = np.array(mp[i])
    plt.scatter(dtri[:,0],dtri[:,1])
    plt.plot(np.array(fdc_seg[i])[:,0],np.array(fdc_seg[i])[:,1])
    tri = Delaunay(dtri,qhull_options="QJ")
    triang = mtri.Triangulation(dtri[:, 0],dtri[:, 1],triangles=tri.simplices)
    plt.triplot(dtri[:, 0], dtri[:, 1], tri.simplices,lw=0.5, color='red')
plt.show()

polygon shapesresulted triangle mesh

Answer 1

例程scipy.spatial.Delaunay（）对提供给算法的点的凸包创建三角剖分，因此需要这些额外的三角形。要获得所需的结果，（1）需要希望删除多边形外部的三角形，（2）需要希望多边形的边都实际存在于Delaunay三角剖分中

另一种方法是使用Triangle，它有几个python包装器here和here。该代码构建多边形的约束Delaunay三角剖分，并删除外部三角形