Skip to content

Instantly share code, notes, and snippets.

@afabri
Created November 9, 2022 16:40
Show Gist options
  • Save afabri/7cef1bc991eb334c6697ca2d0d3a6dd7 to your computer and use it in GitHub Desktop.
Save afabri/7cef1bc991eb334c6697ca2d0d3a6dd7 to your computer and use it in GitHub Desktop.
boost::kruskal_minimum_spanning_tree for a Polyhedron without points
#include <CGAL/Polyhedron_3.h>
#include <boost/graph/graph_traits.hpp>
#include <CGAL/boost/graph/kruskal_min_spanning_tree.h>
#include <CGAL/Simple_cartesian.h>
struct empty {};
struct traits {
using Point_3 = empty;
using Plane_3 = empty;
using Construct_opposite_plane_3 = empty;
Construct_opposite_plane_3 construct_opposite_plane_3_object() {
return {};
}
};
using polyhedron = CGAL::Polyhedron_3<traits>;
//using polyhedron = CGAL::Polyhedron_3<CGAL::Simple_cartesian<double>>;
int main() {
using vertex_descriptor = typename boost::graph_traits<polyhedron>::vertex_descriptor;
using vertex_iterator = typename boost::graph_traits<polyhedron>::vertex_iterator;
using edge_descriptor = typename boost::graph_traits<polyhedron>::edge_descriptor;
using vertex_index_map = std::map<vertex_descriptor, int>;
using vertex_index_pmap = boost::associative_property_map<vertex_index_map>;
// using edge_weight_map = std::map<edge_descriptor, double>;
// using edge_weight_pmap = boost::associative_property_map<edge_weight_map>;
using edge_weight_pmap = CGAL::Constant_property_map<edge_descriptor,double>;
auto poly = polyhedron();
vertex_index_map index_map;
vertex_index_pmap index_pmap(index_map);
// edge_weight_map weight_map;
// edge_weight_pmap weight_pmap;
edge_weight_pmap weight_pmap(1.0);
vertex_iterator vb, ve;
int index = 0;
for(boost::tie(vb, ve)=vertices(poly); vb!=ve; ++vb){
index_pmap[*vb] = index++;
}
std::list<edge_descriptor> mst;
boost::kruskal_minimum_spanning_tree(poly, std::back_inserter(mst), boost::vertex_index_map(index_pmap).weight_map(weight_pmap));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment