无法使用 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 shapes resulted triangle mesh

Answer 1

例程 scipy.spatial.Delaunay() 创建了提供给算法的点的凸包的三角剖分，因此这些额外的三角形是预期的。为了获得您正在寻找的结果，（1）您需要希望删除多边形外部的三角形，并且（2）您需要希望多边形的边缘都实际存在于 Delaunay 三角剖分中。

另一种方法是使用 Triangle which has a several python wrappers, here and here。该代码构建多边形的约束 Delaunay 三角剖分并删除外部三角形。

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

Fail to generate correct triangle mesh inside of a concaved polygon using scipy in Python

python

scipy

mesh

delaunay