CGAL中Polygon_Set_2插入多边形时的内核选择问题

在使用CGAL进行几何计算时，开发者可能会遇到一个常见的陷阱：当尝试将多边形插入到多边形集合(Polygon_Set_2)时，程序可能会抛出预条件(precondition)异常。本文将深入分析这一问题的根源，并提供解决方案。

问题现象

当开发者使用Simple_cartesian<double>内核创建多边形并尝试将其插入到Polygon_set_2中时，程序会抛出如下异常：

CGAL ERROR: precondition violation!
Expr: (m_traits.compare_y_at_x_2_object()(p, cv) == EQUAL) && compare_xy(cv.left(), p) == SMALLER && compare_xy(cv.right(), p) == LARGER
File: /path/to/CGAL/include/CGAL/Arr_segment_traits_2.h
Line: 609

问题根源

这个问题的根本原因在于内核选择不当。CGAL的Polygon_set_2类内部依赖于精确的几何谓词计算，而Simple_cartesian<double>内核使用的是浮点数运算，无法保证几何计算的精确性。

具体来说，Polygon_set_2的实现基于排列(Arrangement)数据结构，它需要精确判断点与曲线之间的关系。当使用浮点内核时，由于浮点运算的舍入误差，可能导致几何谓词计算出现不一致的结果，从而触发预条件检查失败。

解决方案

正确的做法是使用Exact_predicates_exact_constructions_kernel(EPEC内核)。这个内核保证了所有几何谓词计算的精确性，同时只在必要时进行精确构造。

修改后的代码示例如下：

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Polygon_set_2<K> Polygon_set_2;

int main() {
    Polygon_set_2 S;
    std::vector<Point_2> vertices = {
        Point_2(-1.99618, -1.2929),
        Point_2(-2.7071, -1.99618),
        Point_2(-2.00382, -2.7071),
        Point_2(-1.2929, -2.00382)
    };
    Polygon_2 polygon(vertices.begin(), vertices.end());
    S.insert(polygon);
    return 0;
}

内核选择建议

在CGAL中，内核选择对程序的正确性和性能有重要影响。以下是几种常见内核的适用场景：

1. Simple_cartesian：适用于对性能要求极高且可以容忍近似结果的场景
2. Exact_predicates_inexact_constructions_kernel：适用于需要精确谓词但可以接受近似构造的场景
3. Exact_predicates_exact_constructions_kernel：适用于需要完全精确计算的场景，如布尔运算、排列计算等

对于涉及复杂几何运算(如多边形布尔运算、排列计算等)的场景，强烈建议使用EPEC内核，以避免由于数值误差导致的意外行为。

总结

在CGAL中处理多边形集合时，内核选择至关重要。使用不适当的内核可能导致预条件检查失败或其他难以调试的问题。通过理解不同内核的特性和适用场景，开发者可以避免这类问题，编写出既正确又高效的几何算法。