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, but only \(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.
template<typename Direction >
vertex_descriptor	extreme_vertex_3 (const Direction &dir) const
	computes the point of the convex hull whose orthogonal projection onto that direction is maximal and returns the associated 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 ReadablePropertyMap 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 computed. Otherwise, g must be convex. Type: Boolean Default: true
random_seed Define the seed used by the hierarchy. 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	is an input iterator with a value type equivalent to Traits::Point_3
Traits	is 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 >

vertex_descriptor CGAL::Convex_hull_hierarchy< PolygonMesh >::extreme_vertex_3

(

const Direction &

dir

)

const

computes the point of the convex hull whose orthogonal projection onto that direction is maximal and returns the associated vertex.

If not unique, a single vertex is returned.

Template Parameters

Direction

must be a Direction_3 typedef of a CGAL kernel

Parameters

dir	the direction