CGAL 6.1 - Quadtrees, Octrees, and Orthtrees

Loading...
Searching...
No Matches
Modules | Classes | Typedefs
Reference Manual

##

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-25b
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