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

Question

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

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

Answer 2

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 3

If you're getting a convex outline instead of concave, it's probably due to the alpha value passed in. Try using find_optimal_alpha(1) as the alpha value or calculate values relative to the bounding size of the point cloud you're passing in. eg.

Alpha_shape_2 aShape(inPoints.begin(), inPoints.end());
aShape.set_alpha( aShape.find_optimal_alpha(1) );
aShape.set_mode(Alpha_shape_2::REGULARIZED);