c ++：CGAL 2D delauny triangulation：凹形

Question

我目前正在进入CGAL进行一些2D三角测量任务，而且我还有一些简单易用的东西。无论如何我真的不知道如何对凹形进行三角测量，因为现在我总是得到所有点的凸包。基本上我想在mouseClick上添加点类似于它在Illustrator中的工作方式，以便它们的顺序中的所有点都是形状的轮廓。我怎么能用CGAL做到这一点？一般来说如何对凹形进行三角测量的一个简单例子可以让我走上正确的轨道！谢谢！

Answer 1

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

Answer 2

我想你首先需要将多边形partition变成凸片。在此之后，您可以使用以下内容创建每个单独多边形的三角形：

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

如果你得到一个凸起的轮廓而不是凹面，那可能是由于传入的alpha值。尝试使用find_optimal_alpha（1）作为alpha值或计算相对于你传入的点云的边界大小的值。例如。

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