The function convex_hull_3() computes the convex hull of a given set of three-dimensional 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 InputIterator , class Polyhedron_3 , class Traits >
void	CGAL::convex_hull_3 (InputIterator first, InputIterator last, Polyhedron_3 &P, 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 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...

template<class InputIterator , class Polyhedron >
void	CGAL::convex_hull_incremental_3 (InputIterator first, InputIterator beyond, Polyhedron &P, bool test_correctness=false)
	computes the convex hull polyhedron of the three-dimensional points in the range [`first`,`beyond`) and assigns it to `P`. More...

Function Documentation

template<class InputIterator , class Polyhedron_3 , class Traits >

void CGAL::convex_hull_3	(	InputIterator	first,
		InputIterator	last,
		Polyhedron_3 &	P,
		const Traits &	ch_traits = `Default_traits`
	)

computes the convex hull of the set of points in the range [first, last).

The polyhedron P is cleared, then the convex hull is stored in P.

Attention: This function does not compute the plane equations of the faces of P.

Precondition: There are at least four points in the range [first, last) not all of which are collinear.

Template Parameters

InputIterator	must be an input iterator with a value type equivalent to `Traits::Point_3`.
Polyhedron_3	must be a model of `ConvexHullPolyhedron_3`.
Traits	must be a model of the concept `ConvexHullTraits_3`. For the purposes of checking the postcondition that the convex hull is valid, `Traits` should 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.

See Also: convex_hull_incremental_3()

Implementation

The algorithm implemented by these functions is the quickhull algorithm of Barnard et al. [1].

Examples:: Convex_hull_3/quickhull_3.cpp.

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).

The result, which may be a point, a segment, a triangle, or a polyhedron, is stored in ch_object.

Attention: This function does not compute the plane equations of the faces of P in case the result is a polyhedron.

Template Parameters

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` should also be a model of the concept `IsStronglyConvexTraits_3`. Furthermore, `Traits` must define a type `Polyhedron_3` that is a model of `ConvexHullPolyhedron_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.

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.

The polyhedron P is cleared and the convex hull of the set of 3D points is stored in P.

Attention: This function does not compute the plane equations of the faces of P.

Precondition: T.dimension()==3.

Template Parameters

Triangulation	is a CGAL 3D triangulation.
Polyhedron	is an instantiation of `CGAL::Polyhedron_3<Traits>`.

See Also: convex_hull_3

Examples:: Convex_hull_3/dynamic_hull_3.cpp.

template<class InputIterator , class Polyhedron >

void CGAL::convex_hull_incremental_3	(	InputIterator	first,
		InputIterator	beyond,
		Polyhedron &	P,
		bool	test_correctness = `false`
	)

computes the convex hull polyhedron of the three-dimensional points in the range [first,beyond) and assigns it to P.

If test_correctness is set to true, the tests described in [3] are used to determine the correctness of the resulting polyhedron.

Attention: This function is provided for completeness and educational purposes. When an efficient incremental implementation is needed, using Delaunay_triangulation_3 together with convex_hull_3_to_polyhedron_3() is highly recommended.

Template Parameters

InputIterator	must be an input iterator where the value type must be `Polyhedron::Traits::Point`.
Polyhedron	must provide a type `Polyhedron::Traits` that defines the following types `Polyhedron::Traits::R`, which is a model of the representation class `R` required by `Convex_hull_d_traits_3<R>` `Polyhedron::Traits::Point`

See Also: convex_hull_3(); Convex_hull_d

Implementation

This function uses the d-dimensional convex hull incremental construction algorithm [2] with d fixed to 3. The algorithm requires \( O(n^2)\) time in the worst case and \( O(n \log n)\) expected time.

Examples:: Convex_hull_3/incremental_hull_3.cpp.

Functions

Function Documentation