#include <CGAL/KDOP_tree/KDOP_tree.h>

Definition

template<typename KDOPTraits>
class CGAL::KDOP_tree::KDOP_tree< KDOPTraits >

Class KDOP_tree is a static data structure for efficient intersection in 3D.

It builds implicitly a hierarchy of discrete oriented polytopes defined by k half planes (a k-DOP tree) for 3D surface meshes, and can receive intersection queries, provided that the corresponding predicates are implemented in the traits class KDOPTraits. An instance of the class KDOPTraits is internally stored.

See also: KDOPTraits

Examples:: KDOP_tree/kdop_distance_query.cpp, KDOP_tree/kdop_polytopes.cpp, and KDOP_tree/kdop_ray_query.cpp.

Public Member Functions
KDOPTraits::Primitive::Datum_reference	datum (Primitive &p) const
	Returns the datum (geometric object) represented `p`.

Types
typedef KDOPTraits::FT	FT
	Number type of the geometry kernel.

typedef KDOPTraits::Point_3	Point
	Type of a 3D point.

typedef KDOPTraits::Primitive	Primitive
	Type of input primitive.

typedef Primitive::Id	Primitive_id
	Identifier for a primitive in the tree.

typedef Primitives::size_type	size_type
	Unsigned integer size type.

typedef KDOPTraits::Kdop	Kdop
	Type of a k-dop.

typedef Kdop::Direction_type	Direction_type
	Type of direction defined in a k-dop.

typedef KDOPTraits::Point_and_primitive_id	Point_and_primitive_id
	3D Point and Primitive Id type

template<typename Query >
using	Intersection_and_primitive_id = KDOPTraits::Intersection_and_primitive_id< Query >
	An alias to `KDOPTraits::Intersection_and_primitive_id<Query>` More...

Construction
	KDOP_tree (const KDOPTraits &traits=KDOPTraits())
	Construct an empty tree and initialise the internally stored traits class using `traits`. More...

template<typename InputIterator , typename... T>
	KDOP_tree (InputIterator first, InputIterator beyond, T &&...)
	Build the data structure from a sequence of primitives. More...

template<typename... T>
void	build (T &&...)
	After one or more calls to `insert()` the internal data structure of the tree must be reconstructed. More...

Operations
template<typename ConstPrimitiveIterator , typename... T>
void	rebuild (ConstPrimitiveIterator first, ConstPrimitiveIterator beyond, T &&...)
	Equivalent to calling `clear()` and then `insert(first,last,t...)`.

template<typename InputIterator , typename... T>
void	insert (InputIterator first, InputIterator beyond, T &&...)
	Add a sequence of primitives to the set of primitives of the KDOP tree. More...

void	insert (const Primitive &p)
	Add a primitive to the set of primitives of the tree.

	~KDOP_tree ()
	Clear and destroy the tree.

const KDOPTraits &	traits () const
	Return a const reference to the internally stored traits class.

void	clear ()
	Clear the tree.

void	set_kdop_directions (const std::vector< Direction_type > &directions)
	Set user-defined directions for k-dop tree. More...

const Kdop	kdop () const
	Return the kdop of the whole tree. More...

void	kdop_heights (std::vector< typename Kdop::Array_height > &heights)
	Output the support heights of k-dops. More...

size_type	size () const
	Return the number of primitives in the tree.

bool	empty () const
	Return `true`, iff the tree contains no primitive.

Intersection queries
template<typename Query >
bool	do_intersect (const Query &query) const
	Return `true`, iff the query intersects at least one of the input primitives. More...

template<typename Query >
size_type	number_of_intersected_primitives (const Query &query) const
	Return the number of primitives intersected by the query. More...

template<typename Query , typename OutputIterator >
OutputIterator	all_intersected_primitives (const Query &query, OutputIterator out) const
	Output to the iterator the list of all intersected primitives ids. More...

template<typename Query >
boost::optional< Primitive_id >	any_intersected_primitive (const Query &query) const
	Return the intersected primitive id that is encountered first in the tree traversal, iff the query intersects at least one of the input primitives. More...

template<typename Ray , typename SkipFunctor >
boost::optional< Primitive_id >	first_intersected_primitive (const Ray &query, const SkipFunctor &skip) const
	Return the primitive id closest to the source point of the ray query. More...

Intersection computation
template<typename Query , typename OutputIterator >
OutputIterator	all_intersections (const Query &query, OutputIterator out) const
	Output the list of all intersections, as objects of `Intersection_and_primitive_id<Query>::Type`, between the query and the input data to the iterator. More...

template<typename Query >
boost::optional< typename Intersection_and_primitive_id< Query >::Type >	any_intersection (const Query &query) const
	Return the intersection that is encountered first in the tree traversal. More...

template<typename Ray , typename SkipFunctor >
boost::optional< typename Intersection_and_primitive_id< Ray >::Type >	first_intersection (const Ray &query, const SkipFunctor &skip) const
	Return the intersection and primitive id closest to the source point of the ray query. More...

Distance queries
Point	closest_point (const Point &query, const Point &hint) const
	Return the point in the union of all input primitives which is closest to the query. More...

Point	closest_point (const Point &query) const
	Return the poitn in the union of all input primitives which is closest to the query. More...

FT	squared_distance (const Point &query, const Point &hint) const
	Return the minimum squared distance between the query point and all input primitives with a user-defined hint in the input mesh. More...

FT	squared_distance (const Point &query) const
	Return the minimum squared distance between the query point and all input primitives. More...

Point_and_primitive_id	closest_point_and_primitive (const Point &query, const Point_and_primitive_id &hint) const
	Return the point and the primitive which correspond to the minimum distance between the query point and all input primitives. More...

Point_and_primitive_id	closest_point_and_primitive (const Point &query) const
	Return the point and the primitive which correspond to the minimum distance between the query point and all input primitives. More...

Member Typedef Documentation

template<typename KDOPTraits >

template<typename Query >

using CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::Intersection_and_primitive_id = KDOPTraits::Intersection_and_primitive_id<Query>

An alias to KDOPTraits::Intersection_and_primitive_id<Query>

Template Parameters

Query should be the type of primitives.

Constructor & Destructor Documentation

template<typename KDOPTraits >

CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::KDOP_tree ( const KDOPTraits & traits = KDOPTraits() )

Construct an empty tree and initialise the internally stored traits class using traits.

template<typename KDOPTraits >

template<typename InputIterator , typename... T>

CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::KDOP_tree	(	InputIterator	first,
		InputIterator	beyond,
		T &&	...
	)

Build the data structure from a sequence of primitives.

Parameters

first	iterator over first primitive to insert
beyond	past-the-end iterator

It is equivalent to constructing an empty tree and calling insert(first,last,t...). The tree remains empty if the memory allocation is not successful.

Member Function Documentation

template<typename Tr >

template<typename Query , typename OutputIterator >

OutputIterator CGAL::KDOP_tree::KDOP_tree< Tr >::all_intersected_primitives	(	const Query &	query,
		OutputIterator	out
	)		const

Output to the iterator the list of all intersected primitives ids.

This function does not compute the intersection points and is hence faster than the function all_intersections() function below.

Template Parameters

Query must be a type for which do_intersect predicates are defined in the traits class KDOPTraits.

template<typename Tr >

template<typename Query , typename OutputIterator >

OutputIterator CGAL::KDOP_tree::KDOP_tree< Tr >::all_intersections	(	const Query &	query,
		OutputIterator	out
	)		const

Output the list of all intersections, as objects of Intersection_and_primitive_id<Query>::Type, between the query and the input data to the iterator.

do_intersect() predicates and intersections must be defined for Query in the KDOPTraits class.

template<typename KDOPTraits >

template<typename Query >

boost::optional<Primitive_id> CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::any_intersected_primitive ( const Query & query ) const

Return the intersected primitive id that is encountered first in the tree traversal, iff the query intersects at least one of the input primitives.

No particular order is guaranteed over the tree traversal, such that, e.g, the primitive returned is not necessarily the closest from the source point of a ray query.

Template Parameters

Query must be a type for which do_intersect predicates are defined in the traits class KDOPTraits.

template<typename KDOPTraits >

template<typename Query >

boost::optional< typename Intersection_and_primitive_id<Query>::Type > CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::any_intersection ( const Query & query ) const

Return the intersection that is encountered first in the tree traversal.

No particular order is guaranteed over the tree traversal, e.g, the primitive returned is not necessarily the closest from the source point of a ray query. Type Query must be a type for which do_intersect predicates and intersections are defined in the traits class KDOPTraits.

template<typename KDOPTraits >

template<typename... T>

void CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::build ( T && ... )

After one or more calls to insert() the internal data structure of the tree must be reconstructed.

This procedure has a complexity of \(O(n log(n))\), where \(n\) is the number of primitives of the tree. This procedure is called implicitly at the first call to a query member function. You can call build() explicitly to ensure that the next call to query functions will not trigger the reconstruction of the data structure. A call to KDOPTraits::set_shared_data(t...) is made using the internally stored traits.

template<typename Tr >

KDOP_tree< Tr >::Point CGAL::KDOP_tree::KDOP_tree< Tr >::closest_point	(	const Point &	query,
		const Point &	hint
	)		const

Return the point in the union of all input primitives which is closest to the query.

In case there are several closest points, one arbitrarily chosen point is returned.

Template Parameters

query	a point with the same type as 'KDOPTraits::Point_3'.
hint	a user-defined point in the input mesh.

template<typename Tr >

KDOP_tree< Tr >::Point CGAL::KDOP_tree::KDOP_tree< Tr >::closest_point ( const Point & query ) const

Return the poitn in the union of all input primitives which is closest to the query.

Internally call closest_point(query, hint) with the default hint derived from the reference point of the first primitive.

template<typename Tr >

KDOP_tree< Tr >::Point_and_primitive_id CGAL::KDOP_tree::KDOP_tree< Tr >::closest_point_and_primitive	(	const Point &	query,
		const Point_and_primitive_id &	hint
	)		const

Return the point and the primitive which correspond to the minimum distance between the query point and all input primitives.

Template Parameters

query	a point with the same type as 'KDOPTraits::Point_3'.
hint	a user-defined point in the input mesh.

template<typename Tr >

KDOP_tree< Tr >::Point_and_primitive_id CGAL::KDOP_tree::KDOP_tree< Tr >::closest_point_and_primitive ( const Point & query ) const

Return the point and the primitive which correspond to the minimum distance between the query point and all input primitives.

Internally call closest_point_and_primitive(query, hint) with hint derived from the reference point of the first primitive.

template<typename Tr >

template<typename Query >

bool CGAL::KDOP_tree::KDOP_tree< Tr >::do_intersect ( const Query & query ) const

Return true, iff the query intersects at least one of the input primitives.

Template Parameters

Query must be a type for which do_intersect predicates are defined in the traits class KDOPTraits.

template<typename KDOPTraits >

template<typename Ray , typename SkipFunctor >

boost::optional<Primitive_id> CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::first_intersected_primitive	(	const Ray &	query,
		const SkipFunctor &	skip
	)		const

Return the primitive id closest to the source point of the ray query.

Template Parameters

Ray	must be the same as `KDOPTraits::Ray_3` and `do_intersect` predicates and intersections must be defined.
Skip	a functor with an operator `bool operator()(const Primitive_id& id) const` that returns `true` in order to skip the primitive. Default to a functor that always returns `false`.

template<typename KDOPTraits >

template<typename Ray , typename SkipFunctor >

boost::optional< typename Intersection_and_primitive_id<Ray>::Type > CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::first_intersection	(	const Ray &	query,
		const SkipFunctor &	skip
	)		const

Return the intersection and primitive id closest to the source point of the ray query.

Template Parameters

Ray	must be the same as `KDOPTraits::Ray_3` and `do_intersect` predicates and intersections must be defined.
Skip	a functor with an operator `bool operator()(const Primitive_id& id) const` that returns `true` in order to skip the primitive. Default to a functor that always returns `false`.

Note: skip might be given some primitives that are not intersected by query because the intersection test is done after the skip test. Also note that the order the primitives are given to skip is not necessarily the intersection order with query.

template<typename KDOPTraits >

template<typename InputIterator , typename... T>

void CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::insert	(	InputIterator	first,
		InputIterator	beyond,
		T &&	...
	)

Add a sequence of primitives to the set of primitives of the KDOP tree.

InputIterator is any iterator and the parameter pack T are any types such that Primitive has a constructor with the following signature: Primitive(InputIterator, T...).

template<typename KDOPTraits >

const Kdop CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::kdop ( ) const

Return the kdop of the whole tree.

Precondition: '!empty()'

template<typename KDOPTraits >

void CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::kdop_heights ( std::vector< typename Kdop::Array_height > & heights )

Output the support heights of k-dops.

Precondition: '!empty()'

template<typename KDOPTraits >

template<typename Query >

size_type CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::number_of_intersected_primitives ( const Query & query ) const

Return the number of primitives intersected by the query.

Template Parameters

Query must be a type for which do_intersect predicates are defined in the traits class KDOPTraits.

template<typename KDOPTraits >

void CGAL::KDOP_tree::KDOP_tree< KDOPTraits >::set_kdop_directions ( const std::vector< Direction_type > & directions )

Set user-defined directions for k-dop tree.

If this is not called in the construction of the k-dop tree, the default directions will be used according to the number of directions prescribed.

Precondition: 'The number of directions is the same as the prescribed direction number.'

template<typename Tr >

KDOP_tree< Tr >::FT CGAL::KDOP_tree::KDOP_tree< Tr >::squared_distance	(	const Point &	query,
		const Point &	hint
	)		const

Return the minimum squared distance between the query point and all input primitives with a user-defined hint in the input mesh.

template<typename Tr >

KDOP_tree< Tr >::FT CGAL::KDOP_tree::KDOP_tree< Tr >::squared_distance ( const Point & query ) const

Return the minimum squared distance between the query point and all input primitives.

Internally call squared_distance(query, hint) with the default hint derived from the reference point of the first primitive.

Definition

template<typename KDOPTraits> class CGAL::KDOP_tree::KDOP_tree< KDOPTraits >

Public Member Functions

Types

Construction

Operations

Intersection queries

Intersection computation

Distance queries

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<typename KDOPTraits>
class CGAL::KDOP_tree::KDOP_tree< KDOPTraits >