3D Convex Hulls

Susan Hert and Stefan Schirra

A subset S ⊆ ℝ^{3} is convex if for any two points p and q
in the set the line segment with endpoints p and q is contained
in S. The convex hull of a set S
is the smallest convex set containing
S. The convex hull of a set of points P ∈ ℝ^{3} is a convex
polytope with vertices in P. A point in P is an extreme point
(with respect to P) if it is a vertex of
the convex hull of P. A set of points is said to be strongly convex
if it consists of only extreme points.

This chapter describes the functions provided in Cgal for producing convex hulls in three dimensions as well as functions for checking if sets of points are strongly convex are not. One can compute the convex hull of a set of points in three dimensions in one of three ways in Cgal: using a static algorithm, using an incremental construction algorithm, or using a triangulation to get a fully dynamic computation.

The function
*convex_hull_3*
provides an
implementation of the quickhull algorithm [BDH96] for three
dimensions
. There are two versions of this
function available, one that can be used when it is known that the output
will be a polyhedron (*i.e.*, there are more than three points and
they are not all collinear) and one that handles all degenerate cases
and returns a *CGAL::Object*, which may be a point, a segment, a
triangle, or a polyhedron. Both versions accept a range of input
iterators defining the set of points whose convex hull is to be computed
and a traits class defining the geometric types and predicates used in
computing the hull.

The function *convex_hull_3* is parameterized by a traits class,
which specifies the types and geometric primitives to be used in the
computation. If input points from a kernel with exact predicates
and non-exact constructions are used, and a certified result is expected,
the traits *Convex_hull_traits_3<R>* should be used
(*R* being the input kernel). Note that the default traits class takes this into
account.

The function *is_strongly_convex_3*
implements the algorithm of Mehlhorn *et al.* [MNS^{+}96]
to determine if the vertices of a given polytope constitute a strongly convex
point set or not. This function is used in postcondition testing for
*convex_hull_3*
.

File:examples/Convex_hull_3/quickhull_3.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/point_generators_3.h> #include <CGAL/algorithm.h> #include <CGAL/Polyhedron_3.h> #include <CGAL/convex_hull_3.h> #include <vector> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Polyhedron_3<K> Polyhedron_3; typedef K::Segment_3 Segment_3; // define point creator typedef K::Point_3 Point_3; typedef CGAL::Creator_uniform_3<double, Point_3> PointCreator; //a functor computing the plane containing a triangular facet struct Plane_from_facet { Polyhedron_3::Plane_3 operator()(Polyhedron_3::Facet& f) { Polyhedron_3::Halfedge_handle h = f.halfedge(); return Polyhedron_3::Plane_3( h->vertex()->point(), h->next()->vertex()->point(), h->opposite()->vertex()->point()); } }; int main() { CGAL::Random_points_in_sphere_3<Point_3, PointCreator> gen(100.0); // generate 250 points randomly on a sphere of radius 100.0 // and copy them to a vector std::vector<Point_3> points; CGAL::copy_n( gen, 250, std::back_inserter(points) ); // 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 " << poly.size_of_vertices() << " vertices" << std::endl; // assign a plane equation to each polyhedron facet using functor Plane_from_facet std::transform( poly.facets_begin(), poly.facets_end(), poly.planes_begin(),Plane_from_facet()); return 0; }

The function *convex_hull_incremental_3*
provides an
interface similar to *convex_hull_3* for the d-dimensional
incremental construction algorithm [CMS93]
implemented by the class *CGAL::Convex_hull_d<R>* that is specialized
to three dimensions. This function accepts an iterator range over a set of
input points and returns a polyhedron, but it does not have a traits class
in its interface. It uses the kernel
class *Kernel* used in the polyhedron type to define an instance of the
adapter traits class *CGAL::Convex_hull_d_traits_3<Kernel>*.

In almost all cases, the static and the dynamic version will be faster than the incremental convex hull algorithm (mainly because of the lack of efficient filtering and the overhead of the general d-dimension). The incremental version is provided for completeness and educational purposes. You should use the dynamic version when you need an efficient incremental convex hull algorithm.

To use the full functionality available with the d-dimensional class
*CGAL::Convex_hull_d<R>* in three dimensions (*e.g.*, the ability
to insert new points and to query if a point lies in the convex hull or not),
you can instantiate the class *CGAL::Convex_hull_d<K>* with the adapter
traits class *CGAL::Convex_hull_d_traits_3<K>*, as shown in the following
example.

File:examples/Convex_hull_3/incremental_hull_class_3.cpp

#include <CGAL/Cartesian.h> #include <CGAL/point_generators_3.h> #include <CGAL/Convex_hull_d.h> #include <CGAL/Convex_hull_d_traits_3.h> #include <CGAL/Convex_hull_d_to_polyhedron_3.h> #include <CGAL/Polyhedron_3.h> #include <CGAL/algorithm.h> #include <vector> #include <cassert> #ifdef CGAL_USE_GMP #include <CGAL/Gmpq.h> typedef CGAL::Gmpq RT; #else #include <CGAL/MP_Float.h> typedef CGAL::Quotient<CGAL::MP_Float> RT; #endif typedef CGAL::Cartesian<RT> K; typedef K::Point_3 Point_3; typedef CGAL::Polyhedron_3< K> Polyhedron_3; typedef CGAL::Convex_hull_d_traits_3<K> Hull_traits_3; typedef CGAL::Convex_hull_d< Hull_traits_3 > Convex_hull_3; typedef CGAL::Creator_uniform_3<double, Point_3> Creator; int main () { Convex_hull_3 CH(3); // create instance of the class with dimension == 3 // generate 250 points randomly on a sphere of radius 100 // and insert them into the convex hull CGAL::Random_points_in_sphere_3<Point_3, Creator> gen(100); for (int i = 0; i < 250 ; i++, ++gen) CH.insert(*gen); assert(CH.is_valid()); // define polyhedron to hold convex hull and create it Polyhedron_3 P; CGAL::convex_hull_d_to_polyhedron_3(CH,P); std::cout << "The convex hull has " << P.size_of_vertices() << " vertices" << std::endl; return 0; }

Fully dynamic maintenance of a convex hull can be achieved by using the
class *CGAL::Delaunay_triangulation_3*. This class supports insertion
and removal of points (*i.e.*, vertices of the triangulation) and the
convex hull edges are simply the finite edges of infinite faces.
The following example illustrates the dynamic construction of a convex hull.
First, random points from a sphere of a certain radius are generated and are
inserted into a triangulation. Then the number of points of the convex hull
are obtained by counting the number of triangulation vertices incident to the
infinite vertex. Some of the points are removed and then the number of points
remaining on the hull are determined. Notice that the vertices incident to the
infinite vertex of the triangulation are on the convex hull but it may be that
not all of them are vertices of the hull.

File:examples/Convex_hull_3/dynamic_hull_3.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/point_generators_3.h> #include <CGAL/Delaunay_triangulation_3.h> #include <CGAL/Polyhedron_3.h> #include <CGAL/convex_hull_3_to_polyhedron_3.h> #include <CGAL/algorithm.h> #include <list> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef K::Point_3 Point_3; typedef CGAL::Delaunay_triangulation_3<K> Delaunay; typedef Delaunay::Vertex_handle Vertex_handle; typedef CGAL::Polyhedron_3<K> Polyhedron_3; int main() { CGAL::Random_points_in_sphere_3<Point_3> gen(100.0); std::list<Point_3> points; // generate 250 points randomly on a sphere of radius 100.0 // and insert them into the triangulation CGAL::copy_n(gen, 250, std::back_inserter(points) ); Delaunay T; T.insert(points.begin(), points.end()); std::list<Vertex_handle> vertices; T.incident_vertices(T.infinite_vertex(), std::back_inserter(vertices)); std::cout << "This convex hull of the 250 points has " << vertices.size() << " points on it." << std::endl; // remove 25 of the input points std::list<Vertex_handle>::iterator v_set_it = vertices.begin(); for (int i = 0; i < 25; i++) { T.remove(*v_set_it); v_set_it++; } //copy the convex hull of points into a polyhedron and use it //to get the number of points on the convex hull Polyhedron_3 chull; CGAL::convex_hull_3_to_polyhedron_3(T,chull); std::cout << "After removal of 25 points, there are " << chull.size_of_vertices() << " points on the convex hull." << std::endl; return 0; }

In the following, we compare the running times of the three approaches to compute 3D convex hulls.
For the static version (using *CGAL::convex_hull_3*) and the dynamic version
(using *CGAL::Delaunay_triangulation_3* and *CGAL::convex_hull_3_to_polyhedron_3*), the kernel
used was *CGAL::Exact_predicates_inexact_constructions_kernel*. For the incremental version
(using *CGAL::convex_hull_incremental_3*), the kernel used was *CGAL::Exact_predicates_exact_constructions_kernel*.

To compute the convex hull of a million of random points in a unit ball the static approach needed 1.63s, while the dynamic and incremental approaches needed 9.50s and 11.54s respectively. To compute the convex hull of the model of Figure 16.1 featuring 192135 points, the static approach needed 0.18s, while the dynamic and incremental approaches needed 1.90s and 6.80s respectively.

The measurements have been performed using Cgal 3.9, using the Gnu C`++` compiler version 4.3.5, under Linux (Debian distribution),
with the compilation options `-O3 -DCGAL_NDEBUG`. The computer used was equipped with a 64bit Intel Xeon 2.27GHz processor and 12GB of RAM.

Next: Reference Manual

CGAL Open Source Project.
Release 3.9.
26 September 2011.