[ACCEPTED]-Delaunay triangulating the 2d polygon with holes-medial-axis
It sounds like you want constrained Delaunay triangulation. The "holes" can 3 be implemented by constraining input edges 2 to remain unbroken in the triangulation.
See 1 the Triangle and poly2tri projects for implementations.
Here's one of the methods I came up with 4 when doing navmesh for an RTS game. Note 3 that it is homebrew, no third-party tools 2 were used, it took me about 3 weeks to implement 1 and bugfix:
- Feed all points into Delaunay triangulation (to get most uniform triangles)
- Check along holes outlines and flip polygon pairs produced by Delaunay to match outlines
- Clip holes innards
Result (plz ignore purple outlines):
More Related questions