|
CGAL 4.5 - 3D Convex Hulls
|
|
CGAL 4.5 - 3D Convex Hulls
|
A subset \( S \subseteq \mathbb{R}^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 \in \mathbb{R}^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 [1] for three dimensionsquickhull, 3D. 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 an 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. [3] 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().
The following program computes the convex hull of a set of 250 random points chosen from a sphere of radius 100. We assume that the points are not all identical and not all collinear, thus we directly use a polyhedron as output. Note the usage of the functor Plane_from_facet together with std::transform() to compute the equations of the plane of each facet of the convex hull.
File Convex_hull_3/quickhull_3.cpp
The function convex_hull_incremental_3() provides an interface similar to convex_hull_3() for the d-dimensional incremental construction algorithm [2] implemented by the class 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 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 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 Convex_hull_d<K> with the adapter traits class Convex_hull_d_traits_3<K>, as shown in the following example.
File Convex_hull_3/incremental_hull_class_3.cpp
Fully dynamic maintenance of a convex hull can be achieved by using the class 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 Convex_hull_3/dynamic_hull_3.cpp
In the following, we compare the running times of the three approaches to compute 3D convex hulls. For the static version (using convex_hull_3()) and the dynamic version (using Delaunay_triangulation_3 and convex_hull_3_to_polyhedron_3()), the kernel used was Exact_predicates_inexact_constructions_kernel. For the incremental version (using convex_hull_incremental_3()), the kernel used was 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 13.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.
1.8.4