如何从CGAL Arrangement的半边边获取原始母线段？

你提供的基础CGAL线段排列代码如下：

#include <iostream>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2; // Traits for segments
typedef Traits_2::Segment_2 Segment_2;
typedef CGAL::Arrangement_2<Traits_2> Arrangement_2;

int main() {
    Arrangement_2 arrangement;

    std::vector<Segment_2> segments = {
            Segment_2(Kernel::Point_2(0.5, 0), Kernel::Point_2(2, 2)),
            Segment_2(Kernel::Point_2(0, 1.5), Kernel::Point_2(2, 1)),
            Segment_2(Kernel::Point_2(1, 0), Kernel::Point_2(1, 2)),
            Segment_2(Kernel::Point_2(0, 2), Kernel::Point_2(2, 0)),
            Segment_2(Kernel::Point_2(0, 1.5), Kernel::Point_2(2, 2))
    };

    CGAL::insert(arrangement, segments.begin(), segments.end());
    
    std::cout << "Vertices:" << std::endl;
    for (auto vit = arrangement.vertices_begin(); vit != arrangement.vertices_end(); ++vit) {
        std::cout << "(" << vit->point() << ")" << std::endl;
    }

    return 0;
}

核心结论 #

使用默认的Arrangement_2时，CGAL没有内置方法直接从半边边关联到原始母线段——因为默认的线段traits仅存储分割后的子线段信息，不会保留原始插入线段的关联关系。

但可以通过两种标准方案实现需求：

方案1：使用Arrangement_with_history_2 #

CGAL提供的Arrangement_with_history_2类专门用于记录插入的原始曲线信息，能直接关联半边边到其所属的原始母线段。

修改后的代码示例

#include <iostream>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_with_history_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2;
typedef Traits_2::Segment_2 Segment_2;
// 改用带历史记录的排列类
typedef CGAL::Arrangement_with_history_2<Traits_2> Arrangement_with_history_2;

int main() {
    Arrangement_with_history_2 arrangement;

    std::vector<Segment_2> segments = {
            Segment_2(Kernel::Point_2(0.5, 0), Kernel::Point_2(2, 2)),
            Segment_2(Kernel::Point_2(0, 1.5), Kernel::Point_2(2, 1)),
            Segment_2(Kernel::Point_2(1, 0), Kernel::Point_2(1, 2)),
            Segment_2(Kernel::Point_2(0, 2), Kernel::Point_2(2, 0)),
            Segment_2(Kernel::Point_2(0, 1.5), Kernel::Point_2(2, 2))
    };

    // 插入线段，自动记录历史
    CGAL::insert(arrangement, segments.begin(), segments.end());

    // 遍历半边边，关联原始母线段
    std::cout << "Halfedges and their original segments:" << std::endl;
    for (auto eit = arrangement.halfedges_begin(); eit != arrangement.halfedges_end(); ++eit) {
        // 获取原始曲线的句柄
        auto orig_curve_handle = arrangement.history()->original_curve(eit);
        const Segment_2& orig_segment = orig_curve_handle->curve();
        
        std::cout << "Halfedge: (" << eit->source()->point() << ") -> (" << eit->target()->point() << ")"
                  << "\nBelongs to original segment: (" << orig_segment.source() << ") -> (" << orig_segment.target() << ")\n" << std::endl;
    }

    return 0;
}

关键说明

• Arrangement_with_history_2会在插入曲线时自动保留原始曲线的副本，并维护半边边与原始曲线的关联。
• 通过arrangement.history()->original_curve(eit)可以直接获取当前半边边所属的原始母线段句柄，进而拿到原始线段数据。

方案2：自定义Traits携带原始线段标识 #

如果不需要完整的历史记录，也可以自定义线段traits，让每个分割后的子线段携带原始母线段的标识（比如ID、指针等）。

简化示例

#include <iostream>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 BaseSegment_2;

// 自定义带ID的线段类型
struct TaggedSegment {
    BaseSegment_2 seg;
    int original_id; // 原始母线段的ID

    // 实现traits所需的基本接口
    const Point_2& source() const { return seg.source(); }
    const Point_2& target() const { return seg.target(); }
};

// 自定义traits，继承默认的线段traits并替换曲线类型
struct TaggedSegmentTraits : public CGAL::Arr_segment_traits_2<Kernel> {
    typedef TaggedSegment Curve_2;
    typedef BaseSegment_2 X_monotone_curve_2;

    // 实现将自定义Curve转换为X单调曲线的方法
    X_monotone_curve_2 construct_x_monotone_curve(const Curve_2& c) const {
        return c.seg;
    }

    // 其他必要的traits方法可直接继承父类实现
};

typedef CGAL::Arrangement_2<TaggedSegmentTraits> TaggedArrangement_2;

int main() {
    TaggedArrangement_2 arrangement;

    std::vector<TaggedSegment> segments = {
        {{Point_2(0.5, 0), Point_2(2, 2)}, 0},
        {{Point_2(0, 1.5), Point_2(2, 1)}, 1},
        {{Point_2(1, 0), Point_2(1, 2)}, 2},
        {{Point_2(0, 2), Point_2(2, 0)}, 3},
        {{Point_2(0, 1.5), Point_2(2, 2)}, 4}
    };

    // 插入自定义带标签的线段
    CGAL::insert(arrangement, segments.begin(), segments.end());

    // 遍历半边边，获取原始线段ID
    std::cout << "Halfedges and their original segment IDs:" << std::endl;
    for (auto eit = arrangement.halfedges_begin(); eit != arrangement.halfedges_end(); ++eit) {
        // 注意：完整实现需扩展traits的X_monotone_curve类型，使其携带原始ID
        // 此处为简化示例，实际需根据CGAL traits规范完善接口
        std::cout << "Halfedge: (" << eit->source()->point() << ") -> (" << eit->target()->point() << ")"
                  << "\nOriginal segment ID: " << /* 完善traits后可直接获取ID */ << "\n" << std::endl;
    }

    return 0;
}

关键说明

• 这种方案更灵活，适合只需要携带少量标识的场景，但需要熟悉CGAL Arrangement traits的接口规范，确保自定义类型满足traits的要求。
• 若要让半边边存储的X单调曲线也携带原始ID，需要进一步修改traits的X_monotone_curve_2类型。

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