geometry/tools/exampleRationalBallQuickHull3D.cpp

Computation of the convex hull of a set of real points in 3D by Quick Hull algorithm.

# 1000000 points in digital ball of radius 1000 with precision 1024
./examples/geometry/tools/exampleRationalBallQuickHull3D 1000000 1000 1024

outputs

#points=1000000 #vertices=4490 #facets=8975
purge duplicates= 254 ms.
init simplex    = 29 ms.
quickhull core  = 326 ms.
compute vertices= 24 ms.
total time      = 634 ms.

See also

QuickHull algorithm in arbitrary dimension for convex hull and Delaunay cell complex computation

 
#include "DGtal/base/Common.h"
#include "DGtal/geometry/tools/QuickHull.h"
#include "DGtal/shapes/SurfaceMesh.h"
#include "DGtal/io/writers/SurfaceMeshWriter.h"
 
double rand01() { return (double) rand() / (double) RAND_MAX; }
 
using namespace DGtal::Z3i;
int main( int argc, char* argv[] )
{
  int    nb = argc > 1 ? atoi( argv[ 1 ] ) : 100;  // nb points
  double  R = argc > 2 ? atof( argv[ 2 ] ) : 10.0; // radius of ball
  double precision = argc > 3 ? atof( argv[ 3 ] ) : 1024.0; // precision
  // (0) typedefs
  typedef DGtal::ConvexHullRationalKernel< 3 > Kernel3D;
  typedef DGtal::QuickHull< Kernel3D >         QuickHull3D;
  // (1) create range of random points in ball
  std::vector< RealPoint > V;
  const double R2 = R * R;
  for ( int i = 0; i < nb; ) {
    RealPoint p( rand01()*2.0*R - R, rand01()*2.0*R - R, rand01()*2.0*R - R );
    if ( p.squaredNorm() < R2 ) { V.push_back( p ); i++; }
  }
  // (2) compute convex hull
  Kernel3D kernel( precision );
  QuickHull3D hull( kernel );
  hull.setInput( V );
  hull.computeConvexHull();
  std::cout << "#points="    << hull.nbPoints()
            << " #vertices=" << hull.nbVertices()
            << " #facets="   << hull.nbFacets() << std::endl;
  double total_time = 0;
  std::for_each( hull.timings.cbegin(), hull.timings.cend(),
                 [&total_time] ( double t ) { total_time += t; } );
  std::cout << "purge duplicates= " << round(hull.timings[ 0 ]) << " ms." << std::endl;
  std::cout << "init simplex    = " << round(hull.timings[ 1 ]) << " ms." << std::endl;
  std::cout << "quickhull core  = " << round(hull.timings[ 2 ]) << " ms." << std::endl;
  std::cout << "compute vertices= " << round(hull.timings[ 3 ]) << " ms." << std::endl;
  std::cout << "total time      = " << round(total_time) << " ms." << std::endl;
  // (3) build mesh
  std::vector< RealPoint > positions;
  hull.getVertexPositions( positions );
  std::vector< std::vector< std::size_t > > facets;
  hull.getFacetVertices( facets );
  typedef DGtal::SurfaceMesh< RealPoint, RealVector> SMesh;
  SMesh mesh( positions.cbegin(), positions.cend(), facets.cbegin(), facets.cend() );
  // (4) output result as OBJ file
  std::ofstream out( "qhull.obj" );
  DGtal::SurfaceMeshWriter< RealPoint, RealVector >::writeOBJ( out, mesh );
  out.close();
  return 0;
}