CODEWITHSUNDEEP
polygontriangulationdelaunayconcave
Archagon
Archagon

Reputation: 2530

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?

Upvotes: 7

Views: 6869

Answers (2)

Archagon
Archagon

Reputation: 2530

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

Upvotes: 3

Martin Beckett
Martin Beckett

Reputation: 96109

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.

Upvotes: -2

Related Questions