Use Constraint delaunay triangulation to Triangulate a Polygon

4
votes

I have a constraint delaunay triangulation (CDT) algorithm, and I have a polygon ( it could be concave or convex) as input. How can I use that constraint delaunay triangulation algorithm to break the polygon into triangles without introducing new points?

Edit: The union of all the triangles must equal to the polygon. So one can't just take the CDT, along with the boundary as the constraint edge to generate the triangles because this would produce a convex polygon, regardless of whether the input is concave or convex.

1
c#c++computational-geometry
So you are saying you have the algorithm, but you want to know how to use it? – Steven Jeuris
@Steven, I think one can't use CDT directly on a concave polygon because the sum of of the triangulation would be convex. – Graviton
You are right. Can't help you there, I assume you already googled, but perhaps this is useful. – Steven Jeuris
How is this question different from stackoverflow.com/questions/996620/… ? – Ben Voigt

1 Answers

1
votes

The easiest way since you have a polygon and not a point cloud would be to triangulate naively then visit each edge and test to see if it is outside the original polygon using simple line-polygon intersection tests.

Depending on your algorithm you may be able to do this test as part of the triangle subdivision and skip the pass at the end. I'm sure there's a slightly better way but this is the first that springs to mind.

Edit:

I implemented this on my triangulator and it gave wrong results because I don't have constraints implemented. If you ensure that all of your polygon edges are used then I believe it should work.