# [ACCEPTED]-Delaunay triangulating the 2d polygon with holes-medial-axis

Accepted answer

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):

Source:
stackoverflow.com

More Related questions

Cookie Warning

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.