类似于在 CGAL 中计算精确偏移量，我可以计算折线的 "exact buffer" 吗？

Question

是否有任何已经构建并准备好使用的 C++ 算法类似于 CGAL 的 offset_2 函数，但不是计算圆和多边形的 Minkowski 和，而是圆和折线的 Minkowski 和计算（即折线的缓冲区）？

在应用程序中，这是我想做的：

输入一条有n个顶点的折线：([x_0,y_0],[x_1,y_1],...,[x_n-1,y_n-1])
找到这条折线的确切缓冲区（输出是一个可能有洞的多边形）
提取每个单独的圆锥弧以测试与我拥有的其他线的交点。
显示这条缓冲折线

谢谢

编辑：可能的解决方案

我可以只在每个顶点生成一个半径为 r 的圆，并沿每个线段生成一个宽度为 2r 的矩形，然后对它们进行并集吗？

如果我正确理解了 CGAL 文档，我可以得到一个精确的解决方案（即由圆锥弧组成的东西），对吗？如果是这样，将不胜感激一些指导。

Answer 1

因此，根据我建议的解决方案，折线和半径为 r 的圆的 Minkowski 和是每个顶点处的圆或半径 r 和宽度为 [= 的矩形的并集11=]关于每条线段。

在此之后，我使用了 Boolean Set-Operations on General Polygons 以及其中的示例，它方便地采用了矩形圆的并集。其关键特征是使用了 GeneralPolygon_2 概念，这使我能够以线性函数和圆弧的形式获得精确解。

这是我的代码片段（请注意，我输入的多段线使用复数坐标）：

Polygon_set_2 S;
// Generate a Circle for each Vertex
for (int i=0; i<complexPolygon.size(); ++i){
    S.join(construct_polygon(Circle_2(Point_2(real(complexPolygon[i]), imag(complexPolygon[i])),1)));
}
// Generate a Rectangle for Each Ordered Pair of Vertices
for (int i=0; i<complexPolygon.size()-1; ++i){
    complex<double> P1, P2, P12, R1, R2, R3, R4;
    P1 = complexPolygon[i];
    P2 = complexPolygon[i+1];
    P12 = P2-P1;
    R1 = P1 - complex<double>(0,w)*P12/abs(P12);
    R4 = P1 + complex<double>(0,w)*P12/abs(P12);
    R2 = R1 + P12;
    R3 = R4 +P12;

    S.join(construct_polygon(Point_2(real(R1), imag(R1)), Point_2(real(R2), imag(R2)),
                             Point_2(real(R3), imag(R3)), Point_2(real(R4), imag(R4))));
}
fstream minkFile;
minkFile.open("mink.txt",ios::out);//open in write mode
if(minkFile.is_open()){
    list<Polygon_with_holes_2> res;
    S.polygons_with_holes (std::back_inserter (res));
    copy (res.begin(), res.end(),
    ostream_iterator<Polygon_with_holes_2>(minkFile, "\n"));
    cout << endl;
}

类似于在 CGAL 中计算精确偏移量，我可以计算折线的 "exact buffer" 吗？

Similar to Computing the Exact Offset in CGAL, can I compute the "exact buffer" of a polyline?

c++

computational-geometry

cgal