CGAL::Convex_hull_hierarchy< PolygonMesh > Struct Template Reference

#include <CGAL/Convex_hull_hierarchy.h>

Definition

template<class PolygonMesh>
struct CGAL::Convex_hull_hierarchy< PolygonMesh >

This class stores a convex hull in a data structure optimized for fast intersection tests.

More specifically, the structure is optimized for CGAL::extreme_vertex_3(), which is used by CGAL::Convex_hull_3::do_intersect(). The computational complexities of CGAL::extreme_point_3() and consequently CGAL::Convex_hull_3::do_intersect() is \(O(n)\) for a range of points, \(O(\sqrt{n})\) on average for a graph and \(O(\log{n})\) on average for a Convex_hull_hierarchy, where \(n\) is the number of points of the object.

Building this structure has linear complexity and is faster than computing a convex hull, but more costly than a single call to CGAL::Convex_hull_3::do_intersect(). It is therefore relevant when many intersection queries are performed, particularly when a convex hull has a large number of vertices.

To evaluate this class, we generated convex hulls by sampling \(n\) random points on the unit sphere, computing their convex hulls, and performing intersection tests between them.

Average performance measurements (times in milliseconds).

Sphere size	Hull build	Hierarchy build	do_intersect (Range)	do_intersect (Graph)	do_intersect (Hull Hierarchy)
40	0.06431	0.006908	0.00260	0.00174	0.00170
100	0.18069	0.016147	0.00594	0.00260	0.00272
350	0.68038	0.076661	0.01976	0.00735	0.00697
1,000	2.14852	0.207484	0.05664	0.02079	0.01292
3,500	7.49052	0.740683	0.19527	0.04876	0.01842
10,000	22.7057	2.22908	0.54977	0.07595	0.02789
35,000	93.7957	8.512	2.00917	0.13722	0.03730
100,000	399.377	32.0424	5.50728	0.39127	0.05841

Template Parameters

PolygonMesh

The polygon mesh used to construct each level of the hierarchy. Must be a model of VertexListGraph and MutableFaceGraph. An internal property map for CGAL::vertex_point_t must be available, with a value type that is a model of Kernel::Point_3.

Examples

Convex_hull_3/do_intersect_ch3.cpp.

Public Types
using	Mesh = PolygonMesh
	The mesh type.

Public Member Functions
template<typename Graph , typename NamedParameters = parameters::Default_named_parameters>
	Convex_hull_hierarchy (const Graph &g, const NamedParameters &np=parameters::default_values())
	constructor taking the points associated to the vertices of g.
template<typename RangeIterator , typename Traits = Convex_hull_traits_3<GT , Mesh>>
	Convex_hull_hierarchy (RangeIterator begin, RangeIterator end, const Traits &traits=Traits())
	constructor taking the points in the range [first, last).
const PolygonMesh &	mesh () const
	returns a const reference to the mesh stored by the class.
PolygonMesh &	mesh ()
	returns a reference to the mesh stored by the class.
template<typename Direction_3 , typename NamedParameters = parameters::Default_named_parameters>
vertex_descriptor	extreme_vertex_3 (const Direction_3 &dir, const NamedParameters &np=parameters::default_values) const
	constructs the furthest point of the convex hull along the direction and returns the corresponding vertex.

Constructor & Destructor Documentation

Convex_hull_hierarchy() [1/2]

template<class PolygonMesh >

template<typename Graph , typename NamedParameters = parameters::Default_named_parameters>

CGAL::Convex_hull_hierarchy< PolygonMesh >::Convex_hull_hierarchy	(	const Graph &	g,
		const NamedParameters &	np = parameters::default_values()
	)

constructor taking the points associated to the vertices of g.

Template Parameters

Graph	a model of VertexListGraph
NamedParameters	a sequence of named parameters

Parameters

g	the graph
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of g Type: a model of ReadWritePropertyMap whose value type is a point type Default: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in VertexListGraph
compute_convex_hull If set to true, the convex hull of g is compute. Otherwise, g is supposed to be convex. Type: bool Default: true Extra: If set to false, g must be convex.
random_seed Define the seed used by Type: unsigned int Default: The seed used by CGAL::get_default_random().

Convex_hull_hierarchy() [2/2]

template<class PolygonMesh >

template<typename RangeIterator , typename Traits = Convex_hull_traits_3<GT , Mesh>>

CGAL::Convex_hull_hierarchy< PolygonMesh >::Convex_hull_hierarchy	(	RangeIterator	begin,
		RangeIterator	end,
		const Traits &	traits = Traits()
	)

constructor taking the points in the range [first, last).

Template Parameters

RangeIterator	must be an input iterator with a value type equivalent to Traits::Point_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 must also be a model of the concept IsStronglyConvexTraits_3. Furthermore, Traits must define a type PolygonMesh that is a model of MutableFaceGraph.

Member Function Documentation

extreme_vertex_3()

template<class PolygonMesh >

template<typename Direction_3 , typename NamedParameters = parameters::Default_named_parameters>

vertex_descriptor CGAL::Convex_hull_hierarchy< PolygonMesh >::extreme_vertex_3	(	const Direction_3 &	dir,
		const NamedParameters &	np = parameters::default_values
	)		const

constructs the furthest point of the convex hull along the direction and returns the corresponding vertex.

Template Parameters

Direction_3	model of Kernel::Direction_3. The kernel does not require to be the same as the one used by the Mesh
NamedParameters	a sequence of Named Parameters

Parameters

dir	the direction
np	an optional sequence of Named Parameters among the ones listed below

Returns

a boost::graph_traits<Mesh>::vertex_descriptor