\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 5.0.3 - CGAL and the Boost Graph Library
BGL_polyhedron_3/distance.cpp
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/Polyhedron_items_with_id_3.h>
#include <boost/graph/breadth_first_search.hpp>
#include <fstream>
typedef Kernel::Point_3 Point;
typedef boost::graph_traits<Polyhedron>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Polyhedron>::vertex_iterator vertex_iterator;
int main(int argc, char** argv) {
Polyhedron P;
std::ifstream in((argc>1)?argv[1]:"cube.off");
in >> P ;
// associate indices to the vertices using the "id()" field of the vertex.
vertex_iterator vb, ve;
int index = 0;
// boost::tie assigns the first and second element of the std::pair
// returned by boost::vertices to the variables vit and ve
for(boost::tie(vb,ve)=vertices(P); vb!=ve; ++vb ){
vertex_descriptor vd = *vb;
vd->id() = index++;
}
// This is the vector where the distance gets written to
std::vector<int> distance(P.size_of_vertices());
// Here we start at an arbitrary vertex
// Any other vertex could be the starting point
boost::tie(vb,ve)=vertices(P);
vertex_descriptor vd = *vb;
std::cout << "We compute distances to " << vd->point() << std::endl;
// bfs = breadth first search explores the graph
// Just as the distance_recorder there is a way to record the predecessor of a vertex
boost::breadth_first_search(P,
vd,
visitor(boost::make_bfs_visitor(boost::record_distances(make_iterator_property_map(distance.begin(),
get(boost::vertex_index, P)),
boost::on_tree_edge()))));
// Traverse all vertices and show at what distance they are
for(boost::tie(vb,ve)=vertices(P); vb!=ve; ++vb ){
vd = *vb;
std::cout << vd->point() << " is " << distance[vd->id()] << " hops away" << std::endl;
}
return 0;
}