Quadtrees, Octrees and Orthtrees Reference

Jackson Campolattaro, Simon Giraudot, Cédric Portaneri, Tong Zhao, and Pierre Alliez

The Orthtree package provides a data structure that subdivides space, with specializations for 2D (Quadtree) and 3D (Octree), along with a collection of algorithms for operating on these structures.

Introduced in: CGAL 5.3
BibTeX: cgal:cpz-o-25a
License: GPL

Classified Reference Pages

Concepts

• OrthtreeTraits
• OrthtreeTraitsWithData
• OrthtreeTraversal
• CollectionPartitioningOrthtreeTraits

Classes

• CGAL::Quadtree<GeomTraits, PointRange, PointMap>
• CGAL::Octree<GeomTraits, PointRange, PointMap>
• CGAL::Orthtree<GeomTraits, PointRange, PointMap>

Traits

• CGAL::Orthtree_traits<GeomTraits, dimension>
• CGAL::Orthtree_traits_point<GeomTraits, PointRange, PointMap, dimension>
• CGAL::Orthtree_traits_base<GeomTraits>
• CGAL::Orthtree_traits_face_graph<TriangleMesh, VertexPointMap>

Split Predicates

• CGAL::Orthtrees::Maximum_contained_elements
• CGAL::Orthtrees::Maximum_depth
• CGAL::Orthtrees::Maximum_depth_and_maximum_contained_elements

Traversal

• CGAL::Orthtrees::Preorder_traversal
• CGAL::Orthtrees::Postorder_traversal
• CGAL::Orthtrees::Leaves_traversal
• CGAL::Orthtrees::Level_traversal

Modules
	Concepts
	Traits
	Split Predicates
	Traversal

Classes
class	CGAL::Orthtree< GeomTraits >
	A data structure using an axis-aligned hyperrectangle decomposition of dD space for efficient access and computation. More...

Typedefs
template<typename GeomTraits , typename PointRange , typename PointMap = Identity_property_map<typename std::iterator_traits<typename PointRange::iterator>::value_type>, bool cubic_nodes = false>
using	CGAL::Octree = Orthtree< Orthtree_traits_point< GeomTraits, PointRange, PointMap, cubic_nodes, 3 > >
	Alias that specializes the Orthtree class to a 3D octree storing 3D points.
template<typename GeomTraits , typename PointRange , typename PointMap = Identity_property_map <typename std::iterator_traits<typename PointRange::iterator>::value_type>, bool squared_nodes = false>
using	CGAL::Quadtree = Orthtree< Orthtree_traits_point< GeomTraits, PointRange, PointMap, squared_nodes, 2 > >
	Alias that specializes the Orthtree class to a 2D quadtree storing 2D points.

Typedef Documentation

Octree

template<typename GeomTraits , typename PointRange , typename PointMap = Identity_property_map<typename std::iterator_traits<typename PointRange::iterator>::value_type>, bool cubic_nodes = false>

using CGAL::Octree = typedef Orthtree<Orthtree_traits_point<GeomTraits, PointRange, PointMap, cubic_nodes, 3> >

#include <CGAL/Octree.h>

Alias that specializes the Orthtree class to a 3D octree storing 3D points.

Template Parameters

GeomTraits	a model of Kernel
PointRange	a model of Range whose value type is the key type of PointMap and whose iterator type is a model of RandomAccessIterator
PointMap	a model of ReadablePropertyMap whose value type is GeomTraits::Point_3
cubic_nodes	Boolean to enforce cubic nodes

Quadtree

template<typename GeomTraits , typename PointRange , typename PointMap = Identity_property_map <typename std::iterator_traits<typename PointRange::iterator>::value_type>, bool squared_nodes = false>

using CGAL::Quadtree = typedef Orthtree<Orthtree_traits_point<GeomTraits, PointRange, PointMap, squared_nodes, 2> >

#include <CGAL/Quadtree.h>

Alias that specializes the Orthtree class to a 2D quadtree storing 2D points.

Template Parameters

GeomTraits	must be a model of Kernel
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 GeomTraits::Point_2
square_nodes	Boolean to enforce square nodes