如何在CGAL的Triangulation_3上使用Boost的Kruskal算法？

Question

我一直试图弄清楚如何为一个CGAL Triangulation_3形成边描述符，这样我就可以在三角剖分上使用Boost实现Kruskal最小生成树。

我一直在阅读Triangulation_2的参考文档(提供了这里)，但注意到boost::graph_traits<Triangulation_3>不存在实现。当我对此感到困惑时，我发现我可以通过一个邻接列表为边缘描述符提供我自己的实现，如Boost的Kruskal的示例所示，但是在这一步中我迷失了方向，并且不知道这是否是一种足够的方法。

最终，我需要做的似乎是创建一个boost图实现，但对于完成这一步骤所需的资源却感到迷茫。从这里开始，所需的用途是能够遍历此MST，在匹配谓词的特定边缘执行基于图形的最小割集。

//编辑:>

我目前的尝试是通过推送定义为一对顶点迭代索引的单纯形边来创建EMST，权重定义为顶点之间的欧几里德距离(一个带有数据的Point_3 )，使用Boost示例中所示的图结构。

我希望BGL顶点(作为一个带有颜色信息的Point_3 )通过BGL边连接(作为一个单纯形！)(三角剖分后的边缘)。我的最终用途只是要求我遍历点3的某种连续的空间顺序(使用RGB信息)，并将估计的平面分割成满足最大距离(完全连接？)的“补丁”。阈值，或片内距离方差。这并不完全是分割，而是类似的。

// some defns...
using RGBA = std::array<uint16_t, 3>;
using PointData = boost::tuple<
    Point_3,    // Point location; Easting-Altitude-Northing
    Vector_3,   // Estimated Normal Vector at Point
    RGBA,       // Photo Color
    RGBA,       // RANSAC Shape Colorization
    size_t,     // Estimated Patch ID
    RGBA>;      // Estimated Patch Colorization

//
//  Some operations on the points and RANSAC estimation occurs here
//

// iterate through shapes
while (it != shapes.end()) {
        boost::shared_ptr<EfficientRANSAC::Shape> shape = *it;
        std::cout << (*it)->info() << std::endl;

        // generate a random color code for this shape
        RGBA rgb;
        for (int i=0; i<3; i++) {
            rgb[i] = rand()%256;
        }

        // Form triangulation to later convert into Graph representation
        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;

        // Iterate through point indices assigned to each detected shape. 
        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));

            // assign shape diagnostic color info
            boost::get<3>(p) = rgb;

            // insert Point_3 data for triangulation and attach PointData info
            auto vertex = tr.insert(boost::get<0>(p));
            vertex->info() = p;

            index_it++; // next assigned point
        }
        
        std::cout << "Found triangulation with: \n\t" << 
            tr.number_of_vertices() << "\tvertices\n\t" <<
            tr.number_of_edges() << "\tedges\n\t" <<
            tr.number_of_facets() << "\tfacets" << std::endl;

        // build a Graph out of the triangulation that we can do a Minimum-Spanning-Tree on
        using Graph = boost::adjacency_list<
                        boost::vecS,        // OutEdgeList
                        boost::vecS,        // VertexList
                        boost::undirectedS, // Directed
                        boost::no_property, // VertexProperties
                        boost::property< boost::edge_weight_t, int >,  // EdgeProperties
                        boost::no_property, // GraphProperties
                        boost::listS        // EdgeList
                        >;
        using Edge = boost::graph_traits<Graph>::edge_descriptor;
        using E = std::pair< size_t, size_t >; // <: TODO - should be iterator index of vertex in Triangulation_3 instead of size_t?

        std::vector<E> edge_array; // edges should be between Point_3's with attached RGBA photocolor info. 
                                   // It is necessary to later access both the Point_3 and RGBA info for vertices after operations are performed on the EMST
        std::vector<float> weights; // weights are `std::sqrt(CGAL::squared_distance(...))` between these Point_3's

        // Question(?) :> Should be iterating over "finite" edges here? 
        for (auto edge : tr.all_edges()) {
            // insert simplex (!!) edge (between-vertices) here 
            edge_array.push_back(...);
            // generate weight using std::sqrt(CGAL::squared_distance(...))
            weights.push_back(...);
        }

        // build Graph from `edge_array` and `weights`
        Graph g(...);
        // build Euclidean-Minimum-Spanning-Tree (EMST) as list of simplex edges between vertices
        std::list<E> emst;
        boost::kruskal_minimum_spanning_tree(...);

        // - traverse EMST from start of list, performing "cuts" into "patches" when we have hit
        // max patch distance (euclidean) from current "first" vertex of "patch". 
        // - have to be able to access Triangulation_3 vertex info (via `locate`?) here
        // - foreach collection of PointData in patch, assign `patch_id` and diagnostic color info,
        //   then commit individual serialized "patches" collections of Point_3 and RGBA photocolor to database 
        todo!();

        it++; // next shape
    }

使用最小生成树通过三角剖分遍历每个形状的最终目标是将每个RANSAC估计的形状分解成块，用于其他目的。图片示例：

​

Answer 1

你想要点边图还是对偶图，即四面体是BGL顶点，四面体之间的面是BGL边？

对于这两个方面来说，编写图特征类的专门化和一些要导航的自由函数并不难。受到graph_traits 2D版本代码的启发

Answer 2

最终，我需要做的似乎是创建一个boost图实现，但对于完成这一步骤所需的资源却感到迷茫。

算法文档的概念要求：

​

​

您可以放大这里的含义：VertexListGraph和EdgeListGraph。

我发现，我可以通过一个邻接列表为边缘描述符提供我自己的实现，如在Kruskal MST的Boost示例中所示，但是在这一步中我迷路了，并且不知道这是否是一种足够的方法。

把你的尝试作为一个问题来展示会很好，因为它会帮助我们知道你被困在哪里了。现在真的没有代码可以“开始”，所以我很高兴地等待一个新的、更具体的问题。

Answer 3

我找到了一个答案。我在我的Point集合实现中添加了另一个属性(在数组中包含了该点的索引)，并使用该属性在三角剖分中的边缘上迭代以构建图，然后在其上运行EMST算法。

然而，真正的答案是不要这样做--它仍然不能正确工作(不正确的边数，包括边列表中的无限顶点，以及其他问题)。

// Form triangulation to later convert into Graph representation
        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;

        // Iterate through point indices assigned to each detected shape. 
        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));

            // assign shape diagnostic color info
            boost::get<3>(p) = rgb;

            // insert Point_3 data for triangulation and attach PointData info
            TriTraits::Vertex_handle vertex = tr.insert(boost::get<0>(p));
            vertex->info() = p;

            index_it++; // next assigned point
        }
        
        std::cout << "Found triangulation with: \n\t" << 
            tr.number_of_vertices() << "\tvertices\n\t" <<
            tr.number_of_edges() << "\tedges\n\t" <<
            tr.number_of_facets() << "\tfacets" << std::endl;

        // build a Graph out of the triangulation that we can do a Minimum-Spanning-Tree on
        // examples taken from https://www.boost.org/doc/libs/1_80_0/libs/graph/example/kruskal-example.cpp
        using Graph = boost::adjacency_list<
                        boost::vecS,            // OutEdgeList
                        boost::vecS,            // VertexList
                        boost::undirectedS,     // Directed
                        boost::no_property,     // VertexProperties
                        boost::property< boost::edge_weight_t, double >  // EdgeProperties
                        >;
        using Edge = boost::graph_traits<Graph>::edge_descriptor;
        using E = std::pair< size_t, size_t >; // <: TODO - should be iterator index of vertex in Triangulation_3 instead of size_t?

        Graph g(tr.number_of_vertices());
        boost::property_map< Graph, boost::edge_weight_t >::type weightmap = boost::get(boost::edge_weight, g);

        // iterate over finite edges in the triangle, and add these 
        for (
                Triangulation_3::Finite_edges_iterator eit = tr.finite_edges_begin();
                eit != tr.finite_edges_end(); 
                eit++
        ) 
        {
            Triangulation_3::Segment s = tr.segment(*eit);

            Point_3 vtx = s.point(0);
            Point_3 n_vtx = s.point(1);

            // locate the (*eit), get vertex handles?
            // from https://www.appsloveworld.com/cplus/100/204/how-to-get-the-source-and-target-points-from-edge-iterator-in-cgal
            Triangulation_3::Vertex_handle vh1 = eit->first->vertex((eit->second + 1) % 3);
            Triangulation_3::Vertex_handle vh2 = eit->first->vertex((eit->second + 2) % 3);

            double weight = std::sqrt(CGAL::squared_distance(vtx, n_vtx));

            Edge e;
            bool inserted;
            boost::tie(e, inserted)
                = boost::add_edge(
                    boost::get<6>(vh1->info()),
                    boost::get<6>(vh2->info()),
                    g
                );
            weightmap[e] = weight;
        }

        // build Euclidean-Minimum-Spanning-Tree (EMST) as list of simplex edges between vertices
        //boost::property_map<Graph, boost::edge_weight_t>::type weight = boost::get(boost::edge_weight, g);
        std::vector<Edge> spanning_tree;

        boost::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

        // we can use something like a hash table to go from source -> target
        // for each of the edges, making traversal easier. 
        // from there, we can keep track or eventually find a source "key" which
        // does not correspond to any target "key" within the table
        std::unordered_map< size_t, std::vector<size_t> > map = {};

        // iterate minimum spanning tree to build unordered_map (hashtable)
        std::cout << "Found minimum spanning tree of " << spanning_tree.size() << " edges for #vertices " << tr.number_of_vertices() << std::endl;
        for (std::vector< Edge >::iterator ei = spanning_tree.begin();
            ei != spanning_tree.end(); ++ei)
        {

            size_t source = boost::source(*ei, g); 
            size_t target = boost::target(*ei, g);
            // << " with weight of " << weightmap[*ei] << std::endl;

            if ( map.find(source) == map.end() ) {
                map.insert(
                    {
                        source, 
                        std::vector({target})
                    }
                );
            } else {
                std::vector<size_t> target_vec = map[source];
                target_vec.push_back(target);
                map[source] = target_vec;
            }
        }

        // iterate over map to find an "origin" node
        size_t origin = 0; 

        for (const auto& it : map) {
            bool exit_flag = false;
            std::vector<size_t> check_targets = it.second;
            for (size_t target : check_targets) {
                if (map.find(target) == map.end()) {
                    origin = target;
                    exit_flag = true;
                    break;
                }
            }
            if (exit_flag) {
                break;
            }
        }

        std::cout << "Found origin of tree with value: " << origin << std::endl;