c++: CGAL 2D delauny triangulation: Concave Shapes

Question

Hi,

I am currently getting into CGAL for some 2D triangulation tasks and I also got something simple to work allready. Anyhow I dont really get how to triangulate concave shapes since Right now I always get the convex hull of all points. Basically I want to add points on mouseClick similar to how it works in illustrator so that all the points in their order are the outline of the shape. How can I do that with CGAL? A simple example of how to triangulate concave shapes in general would propably put me onto the right track! thanks!

Answer 1

I guess you'll first need to partition the polygon into convex pieces. After this you can create triangles of each individual polygon with something like this:

for (int i = 1; i + 1 < polygon.size(); ++i) {
    const Point_2& v0 = polygon[0];
    const Point_2& v1 = polygon[i];
    const Point_2& v2 = polygon[i + 1];
}

Answer 2

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml