与多边形相交时 CGAL 中的分段错误

Question

我正在编写一个代码，我需要非常频繁地计算两个多边形的重叠面积（一个总是正方形，另一个是简单但通常是非凸多边形）。但是，为此使用 CGAL，我偶尔会遇到分段错误。以下代码提供了一个最小示例。请注意，只要其中一个点坐标移动 0.001，一切正常。

#include <CGAL/Cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_2_algorithms.h>

typedef CGAL::Cartesian<double> K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon;
typedef CGAL::Polygon_with_holes_2<K> PolygonH;

int main()
{    
     // Rectangle
     Point pointsA[] = { Point(0.4,0.35), Point(0.4,0.4), Point(0.45,0.4), Point(0.5,0.35) };

     // Triangle
     Point pointsB[] = { Point(0.428,0.412), Point(0.387,0.389), Point(0.359,0.393) };

     // Convert to CGAL polygon
     Polygon polyA(pointsA, pointsA + 4);
     Polygon polyB(pointsB, pointsB + 3);

     // Intersection
     std::list<PolygonH> polyAB;
     CGAL::intersection(polyA, polyB, std::back_inserter(polyAB));
}

Answer 1

如果第一个多边形始终是凸面的（大多数正方形都是）并且您只关心重叠区域，则可以轻松推出自己的解决方案。

考虑第一个多边形的其中一条边的支撑线。您将针对半平面实施裁剪，让我们假设以 x=0 为界，WLOG。

创建一个空的输出多边形。然后依次尝试第二个多边形的所有边。为每个顶点分配布尔条件 x>=0。如果两个端点的条件不同，则将边与轴 x=0 的交点附加到新多边形；然后，如果边的最终端点的条件为真，也附加它。

最后，您将得到一个新的多边形，它是原始多边形的裁剪版本。如果剪裁的多边形应该断开连接，该算法将生成一个连接的多边形，该多边形沿 x=0 具有额外的连接边。但是对于面积的计算，这完全没有关系。

重复四个剪裁边并使用鞋带公式计算面积。

与多边形相交时 CGAL 中的分段错误

Segmentation fault in CGAL when intersecting polygons

c++

polygon

computational-geometry

overlap

cgal