surface_mesh_dijkstra.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/boost/graph/Dual.h>
#include <CGAL/boost/graph/helpers.h>

#include <iostream>
#include <fstream>

#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

typedef CGAL::Simple_cartesian<double>             Kernel;
typedef Kernel::Point_3                            Point;
typedef CGAL::Surface_mesh<Point>                  Mesh;
typedef CGAL::Dual<Mesh>                           Dual;
typedef boost::graph_traits<Dual>::edge_descriptor edge_descriptor;

template <typename G>
struct noborder {
  noborder() : g(NULL) {} // default-constructor required by filtered_graph
  noborder(G& g) : g(&g) {}

  bool operator()(const edge_descriptor& e) const
  { return !is_border(e,*g); }

  G* g;
};


// A dual border edge has a null_face as the source or target "vertex"
// BGL algorithms won't like that, so we remove border edges through a
// boost::filtered_graph.
typedef boost::filtered_graph<Dual, noborder<Mesh> >   FiniteDual;
typedef boost::graph_traits<Mesh>::vertex_descriptor   vertex_descriptor;
typedef boost::graph_traits<Mesh>::face_descriptor     face_descriptor;
typedef boost::graph_traits<Mesh>::edge_descriptor     edge_descriptor;

int main(int argc, char* argv[])
{
  Mesh primal;
  const char* filename = (argc > 1) ? argv[1] : "data/prim.off";
  std::ifstream in(filename);
  in >> primal;

  Dual dual(primal);
  FiniteDual finite_dual(dual,noborder<Mesh>(primal));

  std::cout << "dual has " << num_vertices(dual) << " vertices" << std::endl;

 // the storage of a property map is in primal
  typedef Mesh::Property_map<face_descriptor,face_descriptor> Predecessor_pmap;
  Predecessor_pmap predecessor_pmap = primal.add_property_map<face_descriptor,face_descriptor>("f:pred").first;

 CGAL::Constant_property_map<edge_descriptor,int> unit_cost_pmap(1);

 face_descriptor source = *(vertices(dual).first);

 boost::dijkstra_shortest_paths(dual,
                                source,
                                boost::weight_map(unit_cost_pmap).
                                predecessor_map(predecessor_pmap));

 for (face_descriptor fd : faces(primal)) {
     while (fd != source) {
         std::cout << fd << " ";
         fd = get(predecessor_pmap, fd);
     }
     std::cout << std::endl;
 }

 return 0;
}