CGAL::Orthtree< Traits_, PointRange_, PointMap_ > Class Template Reference

#include <CGAL/Orthtree.h>

Definition

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
class CGAL::Orthtree< Traits_, PointRange_, PointMap_ >

A data structure using an axis-aligned hybercubic decomposition of dD space for efficient point access and computations.

It builds a hierarchy of nodes which subdivide the space based on a collection of points. Each node represents an axis-aligned hypercubic region of space. A node contains the range of points that are present in the region it defines, and it may contain \(2^{dim}\) other nodes which further subdivide the region.

See also

CGAL::Quadtree

CGAL::Octree

Template Parameters

Traits_	must be a model of OrthtreeTraits
PointRange_	must be a model of range whose value type is the key type of PointMap_
PointMap_	must be a model of ReadablePropertyMap whose value type is Traits_::Point_d

Examples

Orthtree/orthtree_build.cpp.

Classes
class	Node
	represents a single node of the tree. More...

Template Types
typedef PointRange_	PointRange
	Point range.
typedef PointMap_	PointMap
	Point map.

Traits Types
typedef Traits::Dimension	Dimension
	Dimension of the tree.
typedef Traits::FT	FT
	Number type.
typedef Traits::Point_d	Point
	Point type.
typedef Traits::Bbox_d	Bbox
	Bounding box type.
typedef Traits::Sphere_d	Sphere
	Sphere type.

Public Types
typedef Orthtree< Traits, PointRange, PointMap >	Self
	Self typedef for convenience.
typedef Dimension_tag<(2<<(Dimension::value-1))>	Degree
	Degree of the tree (number of children of non-leaf nodes).
typedef std::function< bool(Node)>	Split_predicate
	A predicate that determines whether a node must be split when refining a tree.
typedef unspecified_type	Node_range
	A model of ConstRange whose value type is Node.

Constructor
	Orthtree (PointRange &point_range, PointMap point_map=PointMap(), const FT enlarge_ratio=1.2, Traits traits=Traits())
	creates an orthtree from a collection of points.

Tree Building
void	refine (const Split_predicate &split_predicate)
	recursively subdivides the orthtree until it meets the given criteria.
void	refine (size_t max_depth=10, size_t bucket_size=20)
	Convenience overload that refines an orthtree using a maximum depth and maximum number of points in a node as split predicate.
void	grade ()
	refines the orthtree such that the difference of depth between two immediate neighbor leaves is never more than 1.

Accessors
Node	root () const
	returns the root node.
Node	operator[] (std::size_t index) const
	Convenience function to access the child nodes of the root node by their indices.
std::size_t	depth () const
	returns the deepest level reached by a leaf node in this tree (root being level 0).
template<typename Traversal >
Node_range	traverse (const Traversal &traversal=Traversal()) const
	constructs a node range using a tree-traversal function.
Bbox	bbox (const Node &node) const
	constructs the bounding box of a node.

Queries
Node	locate (const Point &point) const
	finds the leaf node which contains the point p.
template<typename OutputIterator >
OutputIterator	nearest_neighbors (const Point &query, std::size_t k, OutputIterator output) const
	finds the k nearest neighbors of query.
template<typename OutputIterator >
OutputIterator	nearest_neighbors (const Sphere &query, OutputIterator output) const
	finds the points in sphere.
template<typename Query , typename OutputIterator >
OutputIterator	intersected_nodes (const Query &query, OutputIterator output) const
	finds the leaf nodes that intersect with any primitive.

Operators
bool	operator== (const Self &rhs) const
	compares the topology of the orthtree with that of rhs.
bool	operator!= (const Self &rhs) const
	compares the topology of the orthtree with that of rhs.

Constructor & Destructor Documentation

Orthtree()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Orthtree	(	PointRange &	point_range,
		PointMap	point_map = PointMap(),
		const FT	enlarge_ratio = 1.2,
		Traits	traits = Traits()
	)

creates an orthtree from a collection of points.

The constructed orthtree has a root node, with no children, that contains the points passed. That root node has a bounding box that encloses all of the points passed, with padding according to the enlarge_ratio.

That root node is built as a n-cube (square in 2D, cube in 3D, etc.) whose edge size is the longest bounding box edge multiplied by enlarge_ratio. Using an enlarge_ratio>1.0 prevents some points from being exactly on the border of some cells, which can lead to over-refinement.

This single-node orthtree is valid and compatible with all Orthtree functionality, but any performance benefits are unlikely to be realized until refine() is called.

Warning

The input point range is not copied. It is used directly and is rearranged by the Orthtree. Altering the point range after creating the orthtree might leave it in an invalid state.

Parameters

point_range	input point range.
point_map	property map to access the input points.
enlarge_ratio	ratio to which the bounding box should be enlarged.
traits	the traits object.

Member Function Documentation

bbox()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

Bbox CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::bbox

(

const Node &

node

)

const

constructs the bounding box of a node.

Note

The object constructed is not the bounding box of the point subset inside the node, but the bounding box of the node itself (cubic).

intersected_nodes()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

template<typename Query , typename OutputIterator >

OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::intersected_nodes	(	const Query &	query,
		OutputIterator	output
	)		const

finds the leaf nodes that intersect with any primitive.

Note

this function requires the function bool CGAL::do_intersect(QueryType, Traits::Bbox_d) to be defined.

This function finds all the intersecting nodes and returns them as const pointers.

Template Parameters

Query	the primitive class (e.g. sphere, ray)
OutputIterator	a model of OutputIterator that accepts Node objects

Parameters

query	the intersecting primitive.
output	output iterator.

locate()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

Node CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::locate

(

const Point &

point

)

const

finds the leaf node which contains the point p.

Traverses the orthtree and finds the deepest cell that has a domain enclosing the point passed. The point passed must be within the region enclosed by the orthtree (bbox of the root node).

Parameters

point

query point.

Returns

the node which contains the point.

nearest_neighbors() [1/2]

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

template<typename OutputIterator >

OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::nearest_neighbors	(	const Point &	query,
		std::size_t	k,
		OutputIterator	output
	)		const

finds the k nearest neighbors of query.

Nearest neighbors are outputted in order of increasing distance to query.

Template Parameters

OutputIterator

a model of OutputIterator that accept Point_d objects.

Parameters

query	a query point.
k	the number of neighbors.
output	the output iterator.

nearest_neighbors() [2/2]

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

template<typename OutputIterator >

OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::nearest_neighbors	(	const Sphere &	query,
		OutputIterator	output
	)		const

finds the points in sphere.

Nearest neighbors are outputted in order of increasing distance to the center of sphere.

Template Parameters

OutputIterator

a model of OutputIterator that accept Point_d objects.

Parameters

query	query sphere.
output	output iterator.

operator==()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

bool CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::operator==

(

const Self &

rhs

)

const

compares the topology of the orthtree with that of rhs.

Trees may be considered equivalent even if they contain different points. Equivalent trees must have the same bounding box and the same node structure. Node structure is evaluated by comparing the root nodes using the node equality operator.

operator[]()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

Node CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::operator[]

(

std::size_t

index

)

const

Convenience function to access the child nodes of the root node by their indices.

my_tree[5] is equivalent to my_tree.root()[5].

See also

Node::operator[]()

Parameters

index

the index of the child node.

Returns

the accessed node.

refine() [1/2]

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

void CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::refine

(

const Split_predicate &

split_predicate

)

recursively subdivides the orthtree until it meets the given criteria.

The split predicate is a std::function that takes a Node and returns a Boolean value (where true implies that a Node needs to be split, false that the Node should be a leaf).

This function may be called several times with different predicates: in that case, nodes already split are left unaltered, while nodes that were not split and for which split_predicate returns true are split.

Parameters

split_predicate

determines whether or not a node needs to be subdivided.

refine() [2/2]

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

void CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::refine	(	size_t	max_depth = 10,
		size_t	bucket_size = 20
	)

Convenience overload that refines an orthtree using a maximum depth and maximum number of points in a node as split predicate.

This is equivalent to calling refine(Orthtrees::Maximum_depth_and_maximum_number_of_inliers(max_depth, bucket_size)).

The refinement is stopped as soon as one of the conditions is violated: if a node has more inliers than bucket_size but is already at max_depth, it is not split. Similarly, a node that is at a depth smaller than max_depth but already has fewer inliers than bucket_size, it is not split.

Parameters

max_depth	deepest a tree is allowed to be (nodes at this depth will not be split).
bucket_size	maximum points a node is allowed to contain.

traverse()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

template<typename Traversal >

Node_range CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::traverse

(

const Traversal &

traversal = Traversal()

)

const

constructs a node range using a tree-traversal function.

This method allows to iterate on the nodes of the tree with a user-selected order (preorder, postorder, leaves-only, etc.).

Template Parameters

Traversal

model of OrthtreeTraversal that provides functions compatible with the type of the orthree

Parameters

traversal

the instance of Traversal used

Returns

a forward input iterator over the nodes of the tree