如何在CGAL 5.6中计算线段交点并关联对应线段？

CGAL 3.1中的Sweep_line_2类已被弃用，新版本（包括5.6）推荐使用Surface_sweep_2模块实现线段交点计算。要获取每个唯一交点对应的关联线段列表，你需要自定义扫线算法的访问器（Visitor），在扫线过程中记录交点与线段的关联关系，最后对结果进行去重整理。

实现步骤与代码示例 #

以下是完整的实现代码，包含必要的类型定义、自定义访问器以及结果整理逻辑：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_sweep_2_algorithms.h>
#include <CGAL/Surface_sweep_2/Default_visitor.h>
#include <vector>
#include <map>

// 定义内核类型
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;

// 自定义访问器：记录所有交点及对应的线段
struct IntersectionVisitor : public CGAL::Surface_sweep_2::Default_visitor<K> {
    // 存储交点到关联线段列表的映射（自动按坐标去重）
    std::map<Point_2, std::vector<const Segment_2*>> intersection_map;

    // 处理两个线段的交点事件
    void add_intersection(const Point_2& pt, const Segment_2& s1, const Segment_2& s2) override {
        intersection_map[pt].push_back(&s1);
        intersection_map[pt].push_back(&s2);
    }
};

int main() {
    // 示例线段集合
    std::vector<Segment_2> segments = {
        Segment_2(Point_2(0,0), Point_2(2,2)),
        Segment_2(Point_2(0,2), Point_2(2,0)),
        Segment_2(Point_2(1,0), Point_2(1,2)),
        Segment_2(Point_2(0,1), Point_2(2,1))
    };

    // 初始化自定义访问器
    IntersectionVisitor visitor;

    // 执行扫线算法，传递自定义访问器
    CGAL::compute_intersections(segments.begin(), segments.end(), visitor);

    // 输出结果：唯一交点及对应的关联线段
    for (const auto& entry : visitor.intersection_map) {
        const Point_2& pt = entry.first;
        const auto& segs = entry.second;
        std::cout << "交点: (" << pt.x() << ", " << pt.y() << ") 关联线段数量: " << segs.size() << std::endl;
        for (const Segment_2* seg : segs) {
            std::cout << "  线段: (" << seg->source().x() << "," << seg->source().y() << ") -> (" 
                      << seg->target().x() << "," << seg->target().y() << ")" << std::endl;
        }
    }

    return 0;
}

关键说明 #

• 自定义访问器：通过继承Default_visitor并重写add_intersection方法，在每次检测到线段交点时，将交点和对应的线段存入std::map（利用Point_2的可比较性自动去重相同坐标的交点）。
• 结果去重：std::map<Point_2, ...>会自动合并同一坐标的交点条目，确保最终得到的是唯一交点，且每个条目下包含所有经过该点的线段。
• 内核选择：示例中使用Exact_predicates_inexact_constructions_kernel，如果需要更高精度的几何计算，可以替换为Exact_predicates_exact_constructions_kernel。

注意事项 #

• 如果线段集合中存在重合线段或线段端点重合的情况，需要额外处理：默认的add_intersection不会捕获端点重合的情况，若需要包含这类交点，需重写访问器的其他方法（如add_overlapping或处理端点事件的方法）。
• 确保链接CGAL库时包含Surface_sweep_2模块的依赖。

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