Search code examples
polygontriangulationdelaunayconcave

How do I cut triangles out of a concave Delaunay triangulation?


I'm using Delaunay to triangulate a concave polygon, but it fills in the concavities. How do I automatically remove the triangles that are outside the polygon boundaries?


Solution

  • Self-answer: in some cases, this is impossible. I needed to use a constrained Delaunay algorithm: http://www.cs.cmu.edu/~quake/triangle.delaunay.html