Jackson Campolattaro, Simon Giraudot, Cédric Portaneri, Tong Zhao, Pierre Alliez
GeometryFactory, Inria
Tree data structures for partitioning space are a common tool to improve the performance of spatial searches and related tasks. CGAL provides a variety of tree structures suited to different purposes, including the kD tree and the AABB tree. In the next release, three new classic structures will be available: the quadtree, the octree, and the orthtree (the natural generalization to higher dimensions).
The Orthtree Package
CGAL’s newest package, Orthtree, provides a collection of functions for building and refining trees, performing traversals of their nodes and searches using different query types.
Most features are templated such that users can finely tune the behavior of the tree. For example, users can define their own patterns for traversal of the tree, or criteria for refining its structure.
An orthtree is especially useful in situations where the kD Tree is not an option, for example when bounding boxes cannot have high aspect-ratios. The RANSAC algorithm used by CGAL’s Shape Detection package previously depended on its own octree implementation for this reason, and it now uses this package.
Performance
The octree can be constructed linearly faster than the kDTree, but individual searches are linearly slower on average. This may make it a worthwhile option in situations where the tree must be reconstructed often, or is only used a small number of times.
Usage
Building a new octree and refining it with the default criteria can be done with only a few lines of code:
Once the tree is constructed, queries can be performed:
The tree can also be traversed manually, or with the help of a traversal function:
Status and links
The package Orthtree is available in CGAL's master branch and will be part of the upcoming CGAL 5.3 release.
