#include <CGAL/Octree.h>

Definition

template<class Point_range, class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>
class CGAL::Octree::Octree< Point_range, Point_map >

a data structure for efficient computations in 3D space.

It builds a hierarchy of nodes which subdivide the space based on a collection of points. Each node represents an axis aligned cubic region of space. A node contains the range of points that are present in the region it defines, and it may contain eight other nodes which further subdivide the region.

Template Parameters

Point_range	is a range type that provides random access iterators over the indices of a set of points.
Point_map	is a type that maps items in the range to Point data

Examples: Octree/Octree_build_from_Point_set.cpp, Octree/Octree_build_from_Point_vector.cpp, Octree/Octree_build_with_custom_split.cpp, Octree/Octree_find_nearest_neighbor.cpp, Octree/Octree_grade.cpp, Octree/Octree_traversal_manual.cpp, and Octree/Octree_traversal_preorder.cpp.

Public Types
typedef Octree< Point_range, Point_map >	Self
	self typedef for convenience

typedef boost::property_traits< Point_map >::value_type	Point
	The point type is deduced from the type of the property map used.

typedef CGAL::Kernel_traits< Point >::Kernel	Kernel
	The Kernel used is deduced from the point type.

typedef Kernel::FT	FT
	The floating point type is decided by the Kernel.

typedef CGAL::Octree::Node< typename Point_range::iterator >	Node
	The Sub-tree / Octant type.

typedef std::function< bool(const Node &)>	Split_criterion_function
	A function that determines whether a node needs to be split when refining a tree.

typedef boost::iterator_range< Traversal_iterator< const Node > >	Node_range_const
	A range that provides input-iterator access to the nodes of a tree.

typedef std::function< const Node (const Node )>	Node_traversal_method_const
	A function that determines the next node in a traversal given the current one.

Construction, Destruction
	Octree (Point_range &point_range, Point_map point_map=Point_map(), const FT enlarge_ratio=1.2)
	Create an octree from a collection of points. More...

Tree Building
void	refine (const Split_criterion_function &split_criterion)
	subdivide an octree's nodes and sub-nodes until it meets the given criteria More...

void	refine (size_t max_depth=10, size_t bucket_size=20)
	refine an octree using a max depth and max number of points in a node as split criterion More...

void	grade ()
	eliminate large jumps in depth by splitting nodes that are much shallower than their neighbors More...

Accessors
const Node &	root () const
	provides read-only access to the root node, and by extension the rest of the tree More...

const Node &	operator[] (int index) const
	access the child nodes of the root node by their indices More...

std::size_t	max_depth_reached () const
	Finds the deepest level reached by a leaf node in this tree. More...

template<class Traversal >
Node_range_const	traverse (const Traversal &traversal_method=Traversal()) const
	constructs an input range of nodes using a tree walker function More...

const Node &	locate (const Point &p) const
	find the leaf node which would contain a point More...

Bbox	bbox (const Node &node) const
	find the bounding box of a node More...

template<typename Point_output_iterator >
void	nearest_k_neighbors_in_radius (const Point &search_point, FT search_radius_squared, std::size_t k, Point_output_iterator output) const
	find the K points in a tree that are nearest to the search point and within a specific radius More...

template<typename Point_output_iterator >
void	nearest_k_neighbors (const Point &search_point, std::size_t k, Point_output_iterator output) const
	find the K points in a tree that are nearest to the search point More...

template<typename Query , typename Node_output_iterator >
void	intersecting_nodes (const Query &query, Node_output_iterator output) const
	find the leaf nodes that intersect with any primitive More...

Operators
bool	operator== (const Self &rhs) const
	compares the topology of a pair of Octrees More...

bool	operator!= (const Self &rhs) const
	compares the topology of a pair of Octrees More...

Constructor & Destructor Documentation

◆ Octree()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

CGAL::Octree::Octree< Point_range, Point_map >::Octree	(	Point_range &	point_range,
		Point_map	point_map = `Point_map()`,
		const FT	enlarge_ratio = `1.2`
	)

Create an octree from a collection of points.

The resulting octree will have a root node with no children that contains the points passed. That root node will have a bounding box that encloses all of the points passed, with padding according to the enlarge_ratio This single-node octree is valid and compatible with all Octree functionality, but any performance benefits are unlikely to be realized unless the tree is refined.

Parameters

point_range	random access iterator over the indices of the points
point_map	maps the point indices to their coordinate locations
enlarge_ratio	the degree to which the bounding box should be enlarged

Member Function Documentation

◆ bbox()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

Bbox CGAL::Octree::Octree< Point_range, Point_map >::bbox ( const Node & node ) const

find the bounding box of a node

Creates a cubic region representing a node. The size of the region depends on the node's depth in the tree. The location of the region depends on the node's location. The bounding box is useful for checking for collisions with a node.

Parameters

node	the node to determine the bounding box of

Returns: the bounding box defined by that node's relationship to the tree

◆ grade()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

void CGAL::Octree::Octree< Point_range, Point_map >::grade ( )

eliminate large jumps in depth by splitting nodes that are much shallower than their neighbors

This function guarantees that any pair of adjacent nodes has a difference in depth no greater than 1.

Todo:: link to adjacent nodes explanation

◆ intersecting_nodes()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

template<typename Query , typename Node_output_iterator >

void CGAL::Octree::Octree< Point_range, Point_map >::intersecting_nodes	(	const Query &	query,
		Node_output_iterator	output
	)		const

find the leaf nodes that intersect with any primitive

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

Template Parameters

Query	the primitive class (e.g. Sphere_3, Ray_3)
Node_output_iterator	an output iterator type that will accept node pointers

Parameters

query	the primitive to check for intersections
output	the output iterator to add node references to

◆ locate()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

const Node& CGAL::Octree::Octree< Point_range, Point_map >::locate ( const Point & p ) const

find the leaf node which would contain a point

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

Parameters

p	The point to find a node for

Returns: A const reference to the node which would contain the point

◆ max_depth_reached()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

std::size_t CGAL::Octree::Octree< Point_range, Point_map >::max_depth_reached ( ) const

Finds the deepest level reached by a leaf node in this tree.

Returns: the deepest level, where root is 0

◆ nearest_k_neighbors()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

template<typename Point_output_iterator >

void CGAL::Octree::Octree< Point_range, Point_map >::nearest_k_neighbors	(	const Point &	search_point,
		std::size_t	k,
		Point_output_iterator	output
	)		const

find the K points in a tree that are nearest to the search point

This function is equivalent to invoking nearest_k_neighbors_in_radius for an infinite radius. For a tree with K or fewer points, all points in the tree will be returned.

Template Parameters

Point_output_iterator an output iterator type that will accept points

Parameters

search_point	the location to find points near
k	the number of points to find
output	the output iterator to add the found points to (in order of increasing distance)

◆ nearest_k_neighbors_in_radius()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

template<typename Point_output_iterator >

void CGAL::Octree::Octree< Point_range, Point_map >::nearest_k_neighbors_in_radius	(	const Point &	search_point,
		FT	search_radius_squared,
		std::size_t	k,
		Point_output_iterator	output
	)		const

find the K points in a tree that are nearest to the search point and within a specific radius

This function guarantees that there are no closer points than the ones returned, but it does not guarantee that it will return at least K points. For a query where the search radius encloses K or fewer points, all enclosed points will be returned. If the search radius passed is too small, no points may be returned. This function is useful when the user already knows how sparse the points are, or if they don't care about points that are too far away. Setting a small radius may have performance benefits.

Template Parameters

Point_output_iterator an output iterator type that will accept points

Parameters

search_point	the location to find points near
search_radius_squared	the size of the region to search within
k	the number of points to find
output	the output iterator to add the found points to (in order of increasing distance)

◆ operator!=()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

bool CGAL::Octree::Octree< Point_range, Point_map >::operator!= ( const Self & rhs ) const

compares the topology of a pair of Octrees

Parameters

rhs	tree to compare with

Returns: whether the trees have different topology

◆ operator==()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

bool CGAL::Octree::Octree< Point_range, Point_map >::operator== ( const Self & rhs ) const

compares the topology of a pair of Octrees

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.

Todo:: Should I link to that?

Parameters

rhs	tree to compare with

Returns: whether the trees have the same topology

◆ operator[]()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

const Node& CGAL::Octree::Octree< Point_range, Point_map >::operator[] ( int index ) const

access the child nodes of the root node by their indices

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

Parameters

index The index of the child node, as an int

Returns: A reference to the node

◆ refine() [1/2]

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

void CGAL::Octree::Octree< Point_range, Point_map >::refine ( const Split_criterion_function & split_criterion )

subdivide an octree's nodes and sub-nodes until it meets the given criteria

The split criterion can be any function pointer that takes a Node pointer and returns a boolean value (where true implies that a Node needs to be split). It's safe to call this function repeatedly, and with different criterion.

Parameters

split_criterion rule to use when determining whether or not a node needs to be subdivided

◆ refine() [2/2]

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

void CGAL::Octree::Octree< Point_range, Point_map >::refine	(	size_t	max_depth = `10`,
		size_t	bucket_size = `20`
	)

refine an octree using a max depth and max number of points in a node as split criterion

This is equivalent to calling:

refine(Split_criterion::Max_depth_or_bucket_size(max_depth, bucket_size));

This functionality is provided for consistency with older octree implementations which did not allow for custom split criterion.

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

◆ root()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

const Node& CGAL::Octree::Octree< Point_range, Point_map >::root ( ) const

provides read-only access to the root node, and by extension the rest of the tree

Returns: a const reference to the root node of the tree

◆ traverse()

template<class Point_range , class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>

template<class Traversal >

Node_range_const CGAL::Octree::Octree< Point_range, Point_map >::traverse ( const Traversal & traversal_method = Traversal() ) const

constructs an input range of nodes using a tree walker function

The result is a boost range created from iterators that meet the criteria defining a Forward Input Iterator This is completely compatible with standard foreach syntax. Dereferencing returns a const reference to a node.

Todo:: Perhaps I should add some discussion of recommended usage

Template Parameters

Traversal type of the walker rule

Parameters

traversal_method the rule to use when determining the order of the sequence of points produced

Returns: a forward input iterator over the nodes of the tree

Definition

template<class Point_range, class Point_map = Identity_property_map<typename Point_range::iterator::value_type>> class CGAL::Octree::Octree< Point_range, Point_map >

Public Types

Construction, Destruction

Tree Building

Accessors

Operators

Constructor & Destructor Documentation

◆ Octree()

Member Function Documentation

◆ bbox()

◆ grade()

◆ intersecting_nodes()

◆ locate()

◆ max_depth_reached()

◆ nearest_k_neighbors()

◆ nearest_k_neighbors_in_radius()

◆ operator!=()

◆ operator==()

◆ operator[]()

◆ refine() [1/2]

◆ refine() [2/2]

◆ root()

◆ traverse()

template<class Point_range, class Point_map = Identity_property_map<typename Point_range::iterator::value_type>>
class CGAL::Octree::Octree< Point_range, Point_map >