Quadtrees, Octrees, and more in Julia


RegionTrees.jl: Quadtrees, Octrees, and their N-Dimensional Cousins

Build Status codecov

This Julia package is a lightweight framework for defining N-Dimensional region trees. In 2D, these are called region quadtrees, and in 3D they are typically referred to as octrees. A region tree is a simple data structure used to describe some kind of spatial data with varying resolution. Each element in the tree can be a leaf, representing an N-dimensional rectangle of space, or a node which is divided exactly in half along each axis into 2^N children. In addition, each element in a RegionTrees.jl tree can carry an arbitrary data payload. This makes it easy to use RegionTrees to approximate functions or describe other interesting spatial data.


  • Lightweight code with few dependencies (only StaticArrays.jl and Iterators.jl are required)
  • Optimized for speed and for few memory allocations
    • Liberal use of @generated functions lets us unroll most loops and prevent allocating temporary arrays
  • Built-in support for general adaptive sampling techniques


See examples/demo.ipynb for a tour through the API. You can also check out:

[1] Frisken et al. "Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics". SIGGRAPH 2000.


An adaptively sampled distance field, from examples/adaptive_distances.ipynb:

An adaptively sampled model-predictive control problem, from examples/adaptive_mpc.ipynb:

An adaptive distance field in 3D, from AdaptiveDistanceFields.jl:

First Commit


Last Touched

3 days ago


46 commits