DGtal  1.3.beta
geometry/tools/exampleLatticeBallQuickHull3D.cpp

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

# 1000000 points in digital ball of radius 1000
./examples/geometry/tools/exampleLatticeBallQuickHull3D 1000000 1000

outputs

#points=999908 #vertices=4480 #facets=8947
purge duplicates= 281 ms.
init simplex    = 24 ms.
quickhull core  = 336 ms.
compute vertices= 24 ms.
total time      = 665 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"
using namespace DGtal::Z3i;
int main( int argc, char* argv[] )
{
int nb = argc > 1 ? atoi( argv[ 1 ] ) : 100; // nb points
double dR = argc > 2 ? atof( argv[ 2 ] ) : 10.0; // radius of ball
// (0) typedefs
typedef DGtal::QuickHull< Kernel3D > QuickHull3D;
// (1) create range of random points in ball
std::vector< Point > V;
const double R2 = dR * dR;
const int R = (int) ceil( dR );
for ( int i = 0; i < nb; ) {
Point p( rand() % (2*R+1) - R, rand() % (2*R+1) - R, rand() % (2*R+1) - R );
if ( p.squaredNorm() < R2 ) { V.push_back( p ); i++; }
}
// (2) compute convex hull
QuickHull3D hull;
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 );
SMesh mesh( positions.cbegin(), positions.cend(), facets.cbegin(), facets.cend() );
// (4) output result as OBJ file
std::ofstream out( "qhull.obj" );
out.close();
return 0;
}
DGtal::ConvexHullIntegralKernel
Aim: a geometric kernel to compute the convex hull of digital points with integer-only arithmetic.
Definition: QuickHullKernels.h:376
DGtal::SurfaceMesh
Aim: Represents an embedded mesh as faces and a list of vertices. Vertices may be shared among faces ...
Definition: SurfaceMesh.h:91
DGtal::ProbingMode::R
@ R
DGtal::QuickHull
Aim: Implements the quickhull algorithm by Barber et al. , a famous arbitrary dimensional convex hull...
Definition: QuickHull.h:139
DGtal::Z3i
Z3i this namespace gathers the standard of types for 3D imagery.
main
int main(int argc, char **argv)
Definition: testArithmeticDSS-benchmark.cpp:147
DGtal::PointVector< dim, Integer >
DGtal::SurfaceMeshWriter::writeOBJ
static bool writeOBJ(std::ostream &output, const SurfaceMesh &smesh)
SMesh
SurfaceMesh< RealPoint, RealVector > SMesh
Definition: fullConvexitySphereGeodesics.cpp:115