CODEWITHSUNDEEP
pythonscipymeshdelaunay
Zhichen
Zhichen

Reputation: 17

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

I encountered a task in my work that where I need to create triangle mesh inside of several different polygons using Python. Though the polygons are segmentations of a convex hull, each segment itself is in concaved shape. When I tried to use scipy.spatial.Delaunay(), it appears that the algorithm assumes the polygon to be convex and ends up generating triangles outside of the concave hull area. The codes and resulted graph are below.

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

Upvotes: 0

Views: 1218

Answers (1)

Alex
Alex

Reputation: 1132

The routine scipy.spatial.Delaunay() creates a triangulation of the convex hull of the points supplied to the algorithm, so these extra triangles are expected. To get the result that you are looking for, (1) you will need to hope to remove triangles outside your polygon and (2) you need to hope that the edges of your polygon all actually exist in the Delaunay triangulation.

An alternative would be to use Triangle which has a several python wrappers, here and here. That code builds a constrained Delaunay triangulation of a polygon and removes the exterior triangles.

Upvotes: 1

Related Questions