ellipsoid_tree

Exact intersection tests for ellipsoids and friends. Points, boxes, balls, ellipsoids, and simplices in R^d; single pairs, tree-accelerated queries, and tree-vs-tree sweeps. Header-only C++17 with Python bindings; Eigen is the only dependency.

A family of anisotropic ellipsoids partitioned into batches of mutually non-overlapping members (example). The figures throughout are 2D because the built-in visualization is 2D; the library itself is dimension-generic.

The design in one idea

ellipsoid_tree is organized around a small closed system:

Objects. Five geometric types — point, Box, Ball, Ellipsoid, Simplex. A Simplex may be lower-dimensional (a point, segment, or triangle embedded in R^d). Two more types participate as queries only: Segment and Halfspace.

Trees over each type. BoxTree, BallTree, EllipsoidTree, and SimplexTree index a family of objects for logarithmic-time queries (SimplexMesh adds mesh connectivity on top of a cell tree; a point cloud is a BallTree with zero radii).

Intersections at three levels, all built from one table of exact pairwise tests:

The diagonal of the third level is self-collision (tree.self_collision_pairs()), which yields the overlap graph of a family: the input to batch picking. Tree × tree over two meshes' cell trees is mesh × mesh collision, the kernel of supermeshing.

The intersection table

The algorithm behind each cell of intersects (all exact; solver-backed cells to documented tolerance). See the visual gallery of every pair.

Query-only columns: a Segment is tested by the slab method (box), projection (ball), a 1D quadratic (ellipsoid), or coordinate intervals (simplex); a Halfspace is a closed-form support-function comparison against everything.

Conventions: ellipsoids are E(τ) = {x : (x−μ)ᵀ Σ⁻¹ (x−μ) ≤ τ²} with Σ symmetric positive definite and the scale τ passed at call time. All objects are solid and closed, so touching counts as intersecting. Tree queries prune conservatively (an ellipsoid query uses a bounding-box test and then the exact ellipsoid-box QP on survivors), so acceleration never changes answers.

Beyond intersections

• Simplicial meshes (SimplexMesh): point location with barycentric coordinates, closest boundary point, CG1 finite element evaluation, mesh × ellipsoid and mesh × mesh queries.
• Supporting cast: k-nearest-neighbor KDTree, axis-alternating geometric_sort, greedy non-overlapping ellipsoid batch picking.
• Optional zero-dependency 2D visualization (ellipsoid_tree/plot2d.hpp): SVG and PNG figures of objects, trees, queries, and CG1 fields. Every figure in the documentation is drawn with it.

Quick start

#include "ellipsoid_tree/ellipsoid_tree.hpp"
using namespace ellipsoid_tree;

Ellipsoid A{mu_a, Sigma_a}, B{mu_b, Sigma_b};
bool overlap = intersects(A, B, /*tau=*/1.0);

EllipsoidTree tree(family_of_ellipsoids, /*tau=*/1.0);
std::vector<int> hits = tree.collisions(some_box);
auto batches = pick_ellipsoid_batches(tree);

Installing

C++ — three equivalent routes, all ending in target_link_libraries(your_target PRIVATE ellipsoid_tree::ellipsoid_tree):

• vendor or FetchContent this repo and add_subdirectory(ellipsoid_tree);
• or install it: cmake -S . -B build && cmake --install build --prefix <prefix>, then find_package(ellipsoid_tree REQUIRED) from any project with <prefix> on CMAKE_PREFIX_PATH;
• or just add include/ to your include path (header-only; Eigen required).

Eigen is found via find_package(Eigen3), with an automatic pinned download as fallback when building this repo standalone.

Python — pip install ellipsoid-tree (or pip install git+https://github.com/NickAlger/ellipsoid_tree) builds the ellipsoid_tree module via scikit-build-core; points are rows ((n, d) arrays, scipy-style), and figures render inline in Jupyter. Alternatively, build the module without pip via cmake -B build -DELLIPSOID_TREE_BUILD_PYTHON=ON && cmake --build build --target ellipsoid_tree_python. For a worked walkthrough, see the Python quickstart notebook.

Compile-time and memory

ellipsoid_tree is header-only but includes Eigen, so every translation unit that includes an ellipsoid_tree header pays Eigen's compile cost — roughly 1.5 s and ~180 MB of RAM per file (a precompiled header cuts that to ~0.2 s and ~125 MB). This is normal for an Eigen-based library, but it adds up if you include ellipsoid_tree in many files. On a memory-limited machine, don't over-parallelize the build: keep at least ~1 GB of RAM per compile job (for example cmake --build . -j N with N no larger than your RAM in GB), or set up a precompiled header on your side.

Examples ("show, don't tell")

Every page in docs/examples/ is a complete program, its actual output, and the figures it draws, which are regenerated from the code by docs/generate_examples.py and checked in CI:

• Pairwise intersection tests, visually
• Which points of a cloud does an ellipsoid cover?
• EllipsoidTree spatial queries
• Batch picking
• SimplexMesh: location, closest points, mesh × ellipsoid
• Mesh vs mesh cell pairs
• KDTree nearest neighbors and its partition
• Rendering a CG1 finite element field

From Python: non-overlapping ellipsoid batches, in a Jupyter notebook — the batch-picking example via the bindings, with figures rendered inline (GitHub renders the executed notebook).

Building and testing

Header-only: add include/ to your include path. To run the tests and examples:

cmake -S . -B build && cmake --build build -j $(nproc) && ctest --test-dir build
python3 docs/generate_examples.py   # regenerate the example documentation

References and acknowledgements

ellipsoid_tree grew out of the point-spread-function probing developed in N. Alger, T. Hartland, N. Petra, and O. Ghattas, Point spread function approximation of high-rank Hessians with locally supported nonnegative integral kernels, SIAM Journal on Scientific Computing 46(3), 2024, A1658–A1689 — the origin of the non-overlapping ellipsoid batch-picking problem. The algorithms and tools it builds on:

• I. Gilitschenski and U. D. Hanebeck, A Direct Method for Checking Overlap of Two Hyperellipsoids, Sensor Data Fusion: Trends, Solutions, Applications (SDF), 2014 — the ellipsoid–ellipsoid overlap test.
• R. P. Brent, Algorithms for Minimization without Derivatives, Prentice-Hall, 1973 — the scalar minimizer used inside it.
• Eigen for linear algebra; stb_image_write (public domain) for PNG encoding; doctest for testing; doxygen-awesome-css for the API-reference theme.

MIT license.