CODEWITHSUNDEEP
qtcgal
skepticalgeek
skepticalgeek

Reputation: 11

CGAL Convex Hull, with Qt

I am attempting to convert an existing application from C# to C++/Qt. The existing code is using the MIConvexHull library to calculate the convex hull of a set of points in 3-dimensional space. It uses the Faces function to get a list of the faces, and then loops through them to get the individual vertices for each face. I want to do this with the CGAL library, but there doesn't seem to be an obvious way to do this. Creating the convex hull using the convex_hull_ 3 function, but from there it isn't obvious what to do.

I need to iterate through the facets of the resulting polyhedron object. For each facet, I need to iterate through the vertices. For each vertex, I need to extract the x, y and z coordinates, to form a QVector3D object.

Here is a code snippet of the existing C# code. In this case, baseContour is a list of 3D vertices.

var triangulationFaces = MIConvexHull.ConvexHull.Create(baseContour).Faces;
var triangulationPoints = new List<Point3D>();
var triangulationIndices = new List<int>();
int i = 0;
foreach (var f in triangulationFaces)
{
   var x = f.Vertices.Select(p => new Point3D(p.Position[0], p.Position[1],    p.Position[2])).ToList();
   triangulationPoints.AddRange(x);
   triangulationIndices.Add(3 * i);
   triangulationIndices.Add(3 * i + 1);
   triangulationIndices.Add(3 * i + 2);
   i++;
}

I am at a loss for how to do this with the CGAL library. I have read quite a bit of the documentation, but it seems to assume you already have graduate level knowledge of computational geometry, which I do not. Anything to point me in the right direction would be appreciated

Upvotes: 1

Views: 521

Answers (1)

Andreas Fabri
Andreas Fabri

Reputation: 1235

There is an example in the user manual.

I used it to do what you want:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/convex_hull_3.h>
#include <vector>
#include <fstream>
#include <boost/foreach.hpp>

typedef CGAL::Exact_predicates_inexact_constructions_kernel  K;
typedef CGAL::Polyhedron_3<K>                     Polyhedron_3;
typedef K::Point_3                  Point_3;

typedef boost::graph_traits<Polyhedron_3>::vertex_descriptor   vertex_descriptor;
typedef boost::graph_traits<Polyhedron_3>::face_descriptor face_descriptor;

int main(int argc, char* argv[])
{ 
  // get the input points from a file  
  std::ifstream in(argv[1]);
  std::vector<Point_3> points;
  Point_3 p;
  while(in >> p){
    points.push_back(p);
  }

  // define polyhedron to hold convex hull
  Polyhedron_3 poly;

  // compute convex hull of non-collinear points
  CGAL::convex_hull_3(points.begin(), points.end(), poly);

  std::cout << "The convex hull contains " 
            << num_vertices(poly) << " vertices"
            << " and " <<  num_faces(poly) << " faces" << std::endl;

  // A hash map that will associate an index to each vertex
  CGAL::Unique_hash_map<vertex_descriptor,int> index;

  int i = 0;  

  // In case your compiler supports C++11 you can replace
  // use the next line instead of the line with BOOST_FOREACH
  // for(vertex_descriptor vd : vertices(poly)){
  BOOST_FOREACH(vertex_descriptor vd, vertices(poly)){
    std::cout << vd->point() << std::endl;
    index[vd]= i++;
  }

  // loop over the faces and for each face loop over the vertices 
  // Again you can replace with for( ..  : .. )
  BOOST_FOREACH(face_descriptor fd, faces(poly)){
    BOOST_FOREACH(vertex_descriptor vd,  vertices_around_face(halfedge(fd,poly),poly)){
      std::cout << index[vd] << " "; 
    }
    std::cout << std::endl;
  }
  return 0;
}

Upvotes: 0

Related Questions