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

Accepted answer
Score: 11

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.

Score: 4

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:

  1. Feed all points into Delaunay triangulation (to get most uniform triangles)
  2. Check along holes outlines and flip polygon pairs produced by Delaunay to match outlines
  3. Clip holes innards

Result (plz ignore purple outlines):

enter image description here

More Related questions