Use Constraint delaunay triangulation to Triangulate a Polygon

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.

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.