如何在CGAL Triangulation_3上使用Boost的Kruskal最小生成树算法

我一直在尝试为CGAL Triangulation_3构造边描述符，以便用Boost实现的Kruskal最小生成树算法处理该三角剖分。

查过Triangulation_2的参考文档，发现目前没有boost::graph_traits<Triangulation_3>的实现。我参考过Boost的Kruskal MST示例，想通过邻接表自行实现边描述符，但卡在这一步，不确定这个方案是否可行。

最终我意识到需要自行实现一个Boost图，但不清楚具体需要哪些资源。后续我还要遍历这个最小生成树，对符合谓词条件的特定边执行基于图的最小割操作。

补充尝试说明 #

我当前的思路是将单纯形边定义为顶点迭代器索引对，以附带数据的Point_3顶点间的欧氏距离为权重，参考Boost示例构建图来生成欧氏最小生成树（EMST）。

我希望BGL的顶点是附带颜色信息的Point_3，边是三角剖分后的单纯形边。最终需求是遍历含RGB信息的Point_3的连续空间排序，将估计平面分割为满足最大距离阈值或片内距离方差的“面片”，这和常规分割类似但不完全相同。

代码实现片段 #

// 一些定义...
using RGBA = std::array<uint16_t, 3>;
using PointData = boost::tuple<
    Point_3,    // 点坐标：东向-高程-北向
    Vector_3,   // 点处估计法向量
    RGBA,       // 照片颜色
    RGBA,       // RANSAC形状着色
    size_t,     // 估计面片ID
    RGBA>;      // 估计面片着色

//
// 此处执行点云及RANSAC估计相关操作
//

// 遍历所有检测到的形状
while (it != shapes.end()) {
        boost::shared_ptr<EfficientRANSAC::Shape> shape = *it;
        std::cout << (*it)->info() << std::endl;

        // 为当前形状生成随机颜色
        RGBA rgb;
        for (int i=0; i<3; i++) {
            rgb[i] = rand()%256;
        }

        // 构建三角剖分，后续转换为图表示
        using VertexInfoBase = CGAL::Triangulation_vertex_base_with_info_3<
                                    PointData,
                                    Kernel
                                >;
        using TriTraits = CGAL::Triangulation_data_structure_3<
                                VertexInfoBase,
                                CGAL::Delaunay_triangulation_cell_base_3<Kernel>,
                                CGAL::Parallel_tag
                            >;
        using Triangulation_3 = CGAL::Delaunay_triangulation_3<Kernel, TriTraits>;

        Triangulation_3 tr;

        // 遍历当前形状分配的所有点索引
        std::vector<std::size_t>::const_iterator 
            index_it = (*it)->indices_of_assigned_points().begin();

        while (index_it != (*it)->indices_of_assigned_points().end()) {
            PointData& p = *(points.begin() + (*index_it));

            // 为点分配形状诊断颜色
            boost::get<3>(p) = rgb;

            // 插入Point_3到三角剖分，并附加PointData信息
            auto vertex = tr.insert(boost::get<0>(p));
            vertex->info() = p;

            index_it++; // 下一个点
        }
        
        std::cout << "生成的三角剖分包含：\n\t" << 
            tr.number_of_vertices() << "\t个顶点\n\t" <<
            tr.number_of_edges() << "\t条边\n\t" <<
            tr.number_of_facets() << "\t个面" << std::endl;

        // 基于三角剖分构建可用于最小生成树计算的图
        using Graph = boost::adjacency_list<
                        boost::vecS,        // 出边列表类型
                        boost::vecS,        // 顶点列表类型
                        boost::undirectedS, // 无向图
                        boost::no_property, // 顶点属性
                        boost::property< boost::edge_weight_t, int >,  // 边权重属性
                        boost::no_property, // 图属性
                        boost::listS        // 边列表类型
                        >;
        using Edge = boost::graph_traits<Graph>::edge_descriptor;
        using E = std::pair< size_t, size_t >; // TODO：这里应该用Triangulation_3的顶点迭代器索引而非size_t？

        std::vector<E> edge_array; // 边存储为带RGBA照片颜色的Point_3之间的连接
                                   // 后续操作EMST时需要能访问顶点的Point_3和RGBA信息
        std::vector<float> weights; // 权重为两点间的欧氏距离：std::sqrt(CGAL::squared_distance(...))

        // 疑问：这里应该遍历有限边（finite edges）而非所有边？
        for (auto edge : tr.all_edges()) {
            // 插入单纯形边（顶点间的边）
            edge_array.push_back(...);
            // 计算并添加权重
            weights.push_back(...);
        }

        // 从edge_array和weights构建图
        Graph g(...);
        // 构建欧氏最小生成树（EMST），存储为顶点间的单纯形边列表
        std::list<E> emst;
        boost::kruskal_minimum_spanning_tree(...);

        // - 遍历EMST，当面片内顶点与当前面片起始顶点的欧氏距离达到阈值时，执行“切割”生成新面片
        // - 需要能访问Triangulation_3的顶点信息（是否用locate方法？）
        // - 为每个面片中的PointData分配patch_id和诊断颜色，然后将面片的Point_3和RGBA照片颜色序列化后存入数据库
        todo!();

        it++; // 下一个形状
    }

最终目标及效果示例 #

通过三角剖分的最小生成树遍历各形状，最终将RANSAC估计的形状拆分为多个块用于后续处理：

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