CGAL布尔差运算遇非简单多边形崩溃问题求助

问题原因 #

CGAL的CGAL::difference()等布尔集合操作函数，仅支持输入简单多边形（无自交、边不重叠交叉的多边形）。非简单多边形会违反算法的前置条件，直接导致崩溃——底层算法默认输入是合法的简单多边形，没有处理自交情况的逻辑。

你的代码里，Polygon A存在明显自交：顶点序列中(8,4)到(8,9)的线段，和之前(8,10)到(8,4)的线段重叠交叉，直接让A变成非简单多边形。

解决方案 #

1. 先校验多边形合法性 #

调用布尔操作前，必须用Polygon_2::is_simple()检查输入是否为简单多边形。不满足条件的话，绝对不能直接传入布尔函数。

2. 将非简单多边形分割为简单多边形集合 #

用CGAL的CGAL::partition_2函数，把非简单多边形拆成多个简单多边形，再对每个简单多边形执行差运算，最后合并结果。

修改后的核心代码示例：

#include <CGAL/partition_2.h>
#include <CGAL/Partition_traits_2.h>

// 新增类型定义
using PartitionTraits = CGAL::Partition_traits_2<Kernel>;
using PolygonContainer = std::vector<Polygon_2>;

int main(void) {
    // ... 原代码中创建Polygon A和B的部分保持不变 ...

    Pwh_2_container diff;
    PolygonContainer simple_polygons;

    if (!A.is_simple()) {
        std::cout << "Polygon A is non-simple, partitioning...\n";
        // 分割非简单多边形为y单调简单多边形
        CGAL::partition_2(A.vertices_begin(), A.vertices_end(), 
                          std::back_inserter(simple_polygons),
                          CGAL::y_monotone_partition_2<PartitionTraits>());
    } else {
        simple_polygons.push_back(A);
    }

    // 对每个简单多边形执行差运算并合并结果
    for (const auto& poly : simple_polygons) {
        Pwh_2_container temp_diff;
        CGAL::difference(B, poly, std::back_inserter(temp_diff));
        diff.insert(diff.end(), temp_diff.begin(), temp_diff.end());
    }

    // ... 原代码中打印结果的部分保持不变 ...
}

额外注意事项 #

• 确保多边形方向正确：CGAL布尔操作要求多边形为逆时针方向（内部在左侧）。用Polygon_2::is_counterclockwise()检查，若方向错误，调用Polygon_2::reverse()反转。
• 如果分割后的多边形包含孔洞，建议转换为Polygon_with_holes_2类型后再执行布尔操作，避免结果异常。

内容的提问来源于stack exchange，提问作者Bruno Santos