CGAL 4.12.1  3D Convex Hulls

The function convex_hull_3()
computes the convex hull of a given set of threedimensional points.
Two versions of this function are available. The first can be used when it is known that the result will be a polyhedron and the second when a degenerate hull may also be possible.
Functions  
template<class PlaneIterator , class PolygonMesh >  
void  CGAL::halfspace_intersection_3 (PlaneIterator begin, PlaneIterator end, PolygonMesh &pm, boost::optional< Kernel_traits< std::iterator_traits< PlaneIterator >::value_type >::Kernel::Point_3 > > origin=boost::none) 
computes robustly the intersection of the halfspaces defined by the planes contained in the range [begin , end ) without constructing the dual points. More...  
template<class PlaneIterator , class PolygonMesh , class Traits >  
void  CGAL::halfspace_intersection_with_constructions_3 (PlaneIterator pbegin, PlaneIterator pend, PolygonMesh &pm, boost::optional< Kernel_traits< std::iterator_traits< PlaneIterator >::value_type >::Kernel::Point_3 > > origin=boost::none, const Traits &ch_traits=Default_traits) 
computes the intersection of the halfspaces defined by the planes contained in the range [begin , end ). More...  
template<class InputIterator , class PolygonMesh , class Traits >  
void  CGAL::convex_hull_3 (InputIterator first, InputIterator last, PolygonMesh &pm, const Traits &ch_traits=Default_traits) 
computes the convex hull of the set of points in the range [first , last ). More...  
template<class InputIterator , class Traits >  
void  CGAL::convex_hull_3 (InputIterator first, InputIterator last, Object &ch_object, const Traits &ch_traits=Default_traits) 
computes the convex hull of the set of points in the range [first , last ). More...  
template<class Triangulation , class PolygonMesh >  
void  CGAL::convex_hull_3_to_face_graph (const Triangulation &T, PolygonMesh &pm) 
fills a polyhedron with the convex hull of a set of 3D points contained in a 3D triangulation of CGAL. More...  
template<class Triangulation , class Polyhedron >  
void  CGAL::convex_hull_3_to_polyhedron_3 (const Triangulation &T, Polyhedron &P) 
fills a polyhedron with the convex hull of a set of 3D points contained in a 3D triangulation of CGAL. More...  
void CGAL::convex_hull_3  (  InputIterator  first, 
InputIterator  last,  
PolygonMesh &  pm,  
const Traits &  ch_traits = Default_traits 

) 
#include <CGAL/convex_hull_3.h>
computes the convex hull of the set of points in the range [first
, last
).
The polyhedron pm
is cleared, then the convex hull is stored in pm
. Note that the convex hull will be triangulated, that is pm
will contain only triangular facets.
first
, last
) not all of which are collinear.InputIterator  must be an input iterator with a value type equivalent to Traits::Point_3 . 
PolygonMesh  must be a model of MutableFaceGraph . 
Traits  must be a model of the concept ConvexHullTraits_3 . For the purposes of checking the postcondition that the convex hull is valid, Traits must also be a model of the concept IsStronglyConvexTraits_3 . 
If the kernel R
of the points determined by the value type of InputIterator
is a kernel with exact predicates but inexact constructions (in practice we check R::Has_filtered_predicates_tag
is Tag_true
and R::FT
is a floating point type), then the default traits class of convex_hull_3()
is Convex_hull_traits_3<R>
, and R
otherwise.
Polygon_mesh
type.Implementation
The algorithm implemented by these functions is the quickhull algorithm of Barnard et al. [1].
void CGAL::convex_hull_3  (  InputIterator  first, 
InputIterator  last,  
Object &  ch_object,  
const Traits &  ch_traits = Default_traits 

) 
#include <CGAL/convex_hull_3.h>
computes the convex hull of the set of points in the range [first
, last
).
The result, which may be a point, a segment, a triangle, or a polyhedron, is stored in ch_object
. In the case the result is a polyhedron, the convex hull will be triangulated, that is the polyhedron will contain only triangular facets.
InputIterator  must be an input iterator with a value type equivalent to Traits::Point_3 . 
Traits  must be model of the concept ConvexHullTraits_3 . For the purposes of checking the postcondition that the convex hull is valid, Traits must also be a model of the concept IsStronglyConvexTraits_3 . Furthermore, Traits must define a type Polygon_mesh that is a model of MutableFaceGraph . 
If the kernel R
of the points determined by the value type of InputIterator
is a kernel with exact predicates but inexact constructions (in practice we check R::Has_filtered_predicates_tag
is Tag_true
and R::FT
is a floating point type), then the default traits class of convex_hull_3()
is Convex_hull_traits_3<R>
, and R
otherwise.
Polygon_mesh
type. void CGAL::convex_hull_3_to_face_graph  (  const Triangulation &  T, 
PolygonMesh &  pm  
) 
#include <CGAL/convex_hull_3_to_face_graph.h>
fills a polyhedron with the convex hull of a set of 3D points contained in a 3D triangulation of CGAL.
The polyhedron pm
is cleared and the convex hull of the set of 3D points is stored in pm
.
T.dimension()
==3.Triangulation  must be a CGAL 3D triangulation 
PolygonMesh  must be a model of the concept MutableFaceGraph 
convex_hull_3()
link_to_face_graph()
void CGAL::convex_hull_3_to_polyhedron_3  (  const Triangulation &  T, 
Polyhedron &  P  
) 
#include <CGAL/convex_hull_3_to_polyhedron_3.h>
fills a polyhedron with the convex hull of a set of 3D points contained in a 3D triangulation of CGAL.
The polyhedron P
is cleared and the convex hull of the set of 3D points is stored in P
.
convex_hull_3_to_face_graph()
instead.P
.CGAL::Polyhedron_3<Traits>
, and users who want to generate a Surface_mesh
or any other model of a FaceGraph
may use convex_hull_3_to_face_graph()
instead.T.dimension()
==3.Triangulation  is a CGAL 3D triangulation. 
Polyhedron  is an instantiation of CGAL::Polyhedron_3<Traits> . 
convex_hull_3()
link_to_face_graph()
void CGAL::halfspace_intersection_3  (  PlaneIterator  begin, 
PlaneIterator  end,  
PolygonMesh &  pm,  
boost::optional< Kernel_traits< std::iterator_traits< PlaneIterator >::value_type >::Kernel::Point_3 >  ,  
origin  = boost::none 

) 
#include <CGAL/Convex_hull_3/dual/halfspace_intersection_3.h>
computes robustly the intersection of the halfspaces defined by the planes contained in the range [begin
, end
) without constructing the dual points.
The result is stored in the polyhedron pm
. If origin
is given then it must be a point strictly inside the polyhedron. If an interior point is not given then it is computed using a linear program and thus is slower.
This version does not construct the dual points explicitely but uses a special traits class for the function CGAL::convex_hull_3()
to handle predicates on dual points without constructing them.
origin
and the point type of the vertices of PolygonMesh
must come from the same CGAL Kernel.origin
is inside the intersection of halfspaces defined by the range [begin, end)
. PlaneIterator  must be an input iterator where the value type is a model of the concept Kernel::Plane_3 and this plane type must come from the same kernel as the point type. 
PolygonMesh  must be a model of MutableFaceGraph . 
void CGAL::halfspace_intersection_with_constructions_3  (  PlaneIterator  pbegin, 
PlaneIterator  pend,  
PolygonMesh &  pm,  
boost::optional< Kernel_traits< std::iterator_traits< PlaneIterator >::value_type >::Kernel::Point_3 >  ,  
origin  = boost::none , 

const Traits &  ch_traits = Default_traits 

) 
#include <CGAL/Convex_hull_3/dual/halfspace_intersection_with_constructions_3.h>
computes the intersection of the halfspaces defined by the planes contained in the range [begin
, end
).
The result is stored in the polyhedron pm
. If origin
is given then it must be a point strictly inside the polyhedron. If an interior point is not given then it is computed using a linear program and thus is slower. This version constructs explicitly the dual points using the convex hull algorithm parametrized with the given traits class.
PlaneIterator
and the point type of origin
must come from the same CGAL Kernel. origin
is inside the intersection of halfspaces defined by the range [begin, end)
. PlaneIterator  must be an input iterator where the value type is a model of the concept Kernel::Plane_3 and this plane type must come from the same kernel as the point type. 
PolygonMesh  must be a model of MutableFaceGraph . 
Traits  must be a model of the concept ConvexHullTraits_3 . 
halfspace_intersection_3()