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 implements a convex hull with a data structure optimized for finding the extreme point of the convex hull in a given direction.

In particular, this operation is called by CGAL::Convex_hull_3::do_intersect() and therefore, this class is optimized for very fast intersection tests.

Template Parameters

PolygonMesh

The polygon mesh structure used to construct each level of the hierarchy. Must be a model of MutableFaceGraph. An internal property map for CGAL::vertex_point_t must be available, from which the point type Point is deduced. There is no requirement on Point, besides being default constructible and assignable. In typical use cases it will be a 3D point type.

Examples

Convex_hull_3/do_intersect_ch3.cpp.

Public Types
typedef PolygonMesh::Point	Point
	The point type.
typedef PolygonMesh	Mesh
	The mesh type.

Public Member Functions
template<typename Graph , typename NamedParameters = parameters::Default_named_parameters, typename Traits = typename Convex_hull_3::internal::Default_traits_for_Chull_3<Point>::type>
	Convex_hull_hierarchy (const Graph &g, const NamedParameters &np=parameters::default_values(), const Traits &traits=Traits())
	constructor taking the points associated to the vertices of g.
template<typename RangeIterator , typename Traits = typename Convex_hull_3::internal::Default_traits_for_Chull_3<Point>::type>
	Convex_hull_hierarchy (RangeIterator begin, RangeIterator end, const Traits &traits=Traits())
	constructor taking the points in the range [first, last).
template<class Direction_3 , typename NamedParameters = parameters::Default_named_parameters>
Kernel_traits< Direction_3 >::Kernel::Point_3	extreme_point_3 (const Direction_3 &dir, const NamedParameters &np=parameters::default_values) const
	computes the furthest point of the convex hull along the direction.

Constructor & Destructor Documentation

Convex_hull_hierarchy() [1/2]

template<class PolygonMesh >

template<typename Graph , typename NamedParameters = parameters::Default_named_parameters, typename Traits = typename Convex_hull_3::internal::Default_traits_for_Chull_3<Point>::type>

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

constructor taking the points associated to the vertices of g.

Template Parameters

VertexListGraph	a model of VertexListGraph
NamedParameters	a sequence of named parameters
Traits	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.

Parameters

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

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

Convex_hull_hierarchy() [2/2]

template<class PolygonMesh >

template<typename RangeIterator , typename Traits = typename Convex_hull_3::internal::Default_traits_for_Chull_3<Point>::type>

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
NamedParameters	a sequence of Named Parameters
Traits	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.

Optional Named Parameters

point_map a property map associating points to the elements of r Type: a model of ReadablePropertyMap Default: CGAL::Identity_property_map

If the kernel R of the points determined by the value type of RangeIterator 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. 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_point_3()

template<class PolygonMesh >

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

Kernel_traits< Direction_3 >::Kernel::Point_3 CGAL::Convex_hull_hierarchy< PolygonMesh >::extreme_point_3	(	const Direction_3 &	dir,
		const NamedParameters &	np = parameters::default_values
	)		const

computes the furthest point of the convex hull along the direction.

Template Parameters

NamedParameters

a sequence of named parameters

Parameters

dir	the direction
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 the convex hull Type: a model of ReadWritePropertyMap whose value type is a point type Default: If this parameter is omitted, Point must be a 3D point type of the same kernel than dir