15

I want to triangulate the complex (but not self-intersecting) polygon with holes, so that resulting triangles all lay inside the polygon, cover that polygon completely, and obey the Delaunay triangle rules.

Obviously, I could just build the Delaunay triangulation for all points, but I fear that some edges of the polygon will not be included into resulting triangulation.

So, is such triangulation possible? And if yes, how can I do it?

Just in case - I need it to construct the approximation of polygon medial axis (I hope it can be done via connecting all circumference points of resulting triangles).

Rogach
  • 26,050
  • 21
  • 93
  • 172
  • But the set of vertices (and thus its Delaunay triangulation) doesn't determine whether or not the polygon has a hole. Isn't this important to you? – TonyK Apr 13 '11 at 09:23
  • @TonyK - I have several sets of sequential verticles - one for outer polygon, and several sets for inner polygons. – Rogach Apr 13 '11 at 09:30
  • But if you 'build the Delaunay triangulation for all points', you will triangulate inside the holes. How are you going to avoid this? – TonyK Apr 13 '11 at 11:37
  • @TonyK - I hoped to triangulate all dots, and then exclude all triangles that are either outside of polygon, or inside it's holes. – Rogach Apr 13 '11 at 18:51

2 Answers2

11

It sounds like you want constrained Delaunay triangulation. The "holes" can be implemented by constraining input edges to remain unbroken in the triangulation.

See the Triangle and poly2tri projects for implementations.

Kipton Barros
  • 21,002
  • 4
  • 67
  • 80
5

Here's one of the methods I came up with when doing navmesh for an RTS game. Note that it is homebrew, no third-party tools were used, it took me about 3 weeks to implement 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

Kromster
  • 7,181
  • 7
  • 63
  • 111