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

Question

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?

Is this what you actually want to do? The Delaunay edges may cross the polygon edges, so using this to triangulate a polygon is not going to always give you a valid triangulation of the polygon. — , Dec 17 '09 at 00:41

score 3 · Accepted Answer · answered Feb 19 '10 at 09:46

3

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

answered Feb 19 '10 at 09:46

Archagon

2,470
2
25
38

score -2 · Answer 2 · answered Jan 06 '10 at 18:13

You shouldn't, you should find a Delauney routine that handles boundaries correctly.

Alternately you could, assuming you know the edges, go through every triangle and delete those that cross an edge. Search for segment-segment interestion tests for code to do this.

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

2 Answers2