Metadata-Version: 2.4
Name: boostree
Version: 0.1.0
Summary: Drop-in subset of rtree.index backed by Boost.Geometry — ~6× faster on the operations CFD codes need
Keywords: rtree,spatial-index,boost,geometry
Author: PyFR developers
License-Expression: BSL-1.0
License-File: LICENSE
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering
Project-URL: Homepage, https://github.com/PyFR/boostree
Project-URL: Issues, https://github.com/PyFR/boostree/issues
Project-URL: Source, https://github.com/PyFR/boostree
Requires-Python: >=3.10
Requires-Dist: numpy>=1.20
Provides-Extra: test
Requires-Dist: pytest; extra == "test"
Requires-Dist: rtree>=1.0; extra == "test"
Description-Content-Type: text/markdown

# boostree

A fast in-memory R\*-tree index over points or axis-aligned bounding
boxes, backed by
[Boost.Geometry](https://www.boost.org/doc/libs/release/libs/geometry/)
via `pybind11`.

Two surfaces:

1. **Native API** (`boostree.RTree`) — a clean, batched, numpy-first
   interface designed for new code.
2. **rtree.index drop-in** (`boostree.index.Index`,
   `boostree.index.Property`) — method-for-method compatible with the
   subset of the PyPI `rtree` package.

On that subset it's **~6× faster per query** and **~4× faster to
build** than `libspatialindex` (which the PyPI `rtree` package wraps),
plus:

| Feature | `rtree` (PyPI) | `boostree` |
|---|---|---|
| Bulk `nearest` over many query points | yes (`nearest_v`) | yes |
| Bulk `intersection` over many query bboxes | yes (`intersection_v`) | yes |
| GIL released during batch queries | no | yes |
| Free-threaded CPython (PEP 703) | no | yes |
| Bulk `delete` by id-set | no — one at a time, needs original coords | yes |
| Bulk `delete` by bbox range | no | yes |
| `update` (move entry by id) | no — hand-roll `delete` + `insert` | yes |
| `copy.copy` / `copy.deepcopy` | aliases C++ handle | independent deep copy |
| `pickle` | unsupported | works (state is `(ids, mins, maxs)`) |

## Native API

```python
import boostree
import numpy as np

# Build from points or boxes
tree = boostree.RTree.from_points(pts)               # zero-volume boxes
tree = boostree.RTree.from_points(pts, ids=eids)     # with ids
tree = boostree.RTree.from_boxes(mins, maxs)         # explicit boxes
tree = boostree.RTree.from_pairs(items, dim=3)       # iterable form

# k-nearest, rows sorted by ascending distance; optional per-query
# radius cap (radius<=0 disables)
ids, dists = tree.knn(queries, k=8)
ids, dists = tree.knn(queries, k=8, radius=0.5)
ids, dists = tree.knn(queries, k=8, radius=per_query_radii)

# k-nearest under elliptical (Mahalanobis) metrics: transforms maps
# world coordinates into each metric class's frame; radius is then in
# metric-frame units (radius=1.0 keeps hits inside the ellipse)
ids, dists = tree.knn(queries, k=8, transforms=tmats, class_ids=cids)

# Box queries: pass query_max alongside queries (Euclidean only)
ids, dists = tree.knn(qmins, k=4, query_max=qmaxs)

# Bbox-vs-bbox intersection (ids flat, counts per query)
ids, counts = tree.intersect(qmins, qmaxs)

# All queries are batched — no separate single-query method.  For one
# query, just pass a length-1 array
ids, dists = tree.knn(np.array([[0.5, 0.5, 0.5]]), k=4)

# Mutation — batched and id-based, no need to remember the original
# coordinates the way rtree.index requires
tree.delete(ids_to_drop)                             # by id-set
tree.delete_in(qmins, qmaxs)                         # by bbox-range
tree.update(ids, new_points)                         # upsert by id
tree.add(new_ids, new_points)                        # incremental insert

# copy.copy / copy.deepcopy both produce fully independent trees
import copy
tree2 = copy.deepcopy(tree)

# Pickle round-trips through (ids, mins, maxs) — independent of host
# architecture / endianness / pointer width
import pickle
blob = pickle.dumps(tree)
tree3 = pickle.loads(blob)

# Or the same triple directly, e.g. for HDF5 or numpy.savez
ids_arr, mins_arr, maxs_arr = tree.dump()
```

The native API differs from `rtree.index` in several ways:

* **Output shape** is fixed `(n, k)` for both ids and distances, rows
  sorted by ascending distance and padded with `-1` / `+inf`.  No
  variable-length flat returns.
* **Elliptical metrics** are first-class: `knn(..., transforms=...,
  class_ids=...)` runs an exact best-first search under per-query
  Mahalanobis metrics — no oversample-and-re-rank workarounds.
* **`radius` does not mutate** the caller's array (the rtree-compat
  shim does, matching libspatialindex; the native API doesn't because
  callers can read `dists` instead).
* **`radius <= 0` disables the cap** (matches libspatialindex), so the
  zero-radius sentinel works without surprises.
* **`Property` is gone.**  `dim` is inferred from your input; the rtree
  capacities are not user-tunable in Boost's rstar.
* **Mutation is id-based and batched.**  `rtree.index.delete(id, coords)`
  needs the original bbox alongside the id and removes one entry per
  call; `tree.delete(ids)` accepts an array and removes every match in
  one pass.  There's no `update` in `rtree.index` at all — callers
  hand-roll `delete + insert`; `tree.update(ids, points)` does it for
  you with upsert semantics.

## rtree.index drop-in

Existing code that uses `from rtree.index import Index, Property` can
switch to boostree without source changes:

```python
import boostree
boostree.install_rtree_compat()        # one-line shim into sys.modules

# from this point onwards the rtree imports resolve to boostree:
from rtree.index import Index, Property
tree = Index((ids, mins, maxs), properties=Property(dimension=3))
nidxs, counts, dists = tree.nearest_v(qpts, qpts, num_results=8)
ids, counts = tree.intersection_v(qmins, qmaxs)
```

Covered:

* **Bulk batched paths** — bulk-load (numpy `(ids, mins, maxs)` or
  `(id, bbox, obj)`-iterable), `nearest_v` with `max_dists` /
  `return_max_dists`, `intersection_v`.
* **Single-query rtree methods** — `intersection(bbox, objects=False)`,
  `nearest(point, num_results=1)`, `insert(id, coords)`, and
  `delete(eid, coordinates=None)` (boostree ignores the coordinates
  argument since it can look the id up directly; rtree requires it).
* **`copy.copy` / `copy.deepcopy` and `pickle`** — work too, unlike
  upstream `rtree.index` where `copy` aliases the C++ index handle
  and `pickle` isn't supported at all.

Plus three boostree-only batched paths exposed on the same `Index`:

```python
idx.delete_v(ids)                # bulk delete by id
idx.delete_range_v(pmins, pmaxs) # bulk delete by bbox intersection
idx.update_v(ids, pmins, pmaxs)  # bulk upsert
```

Notably **not** supported by either surface:

* dimension other than 2, 3, or 4
* persistent / disk-backed indexes
* user objects carried through queries (`objects=True`)
* arbitrary point types other than float64
* `nearest_v(strict=False)`'s overflow-on-equidistant-ties behaviour
  (we always return exactly `num_results` ids, padded with `-1`)

`Property.index_capacity` / `leaf_capacity` are accepted for API
compatibility but ignored — Boost picks its own internal layout.

## Install

```
pip install boostree
```

Wheels are published for Linux (x86_64, aarch64), macOS (x86_64,
arm64), and Windows (AMD64) on CPython 3.10–3.13.  No Boost or
compiler is required at install time — the minimal Boost.Geometry
header subset is vendored in the source distribution.

To build from source you only need a C++17 compiler and CMake ≥ 3.18:

```
pip install .
```

To rebuild the vendored Boost subset against a newer Boost release,
install `bcp` (e.g. `apt install libboost-tools-dev`) and run:

```
python scripts/vendor_boost.py --boost-root /path/to/boost_x_y_z
```

To build against system Boost instead of the vendored subset, pass
`-DBOOSTREE_USE_SYSTEM_BOOST=ON` to CMake.

OpenMP is auto-detected at build time and used to parallelise batched
queries (`knn`, `nearest_v`, `intersect`, `intersection_v`) across
threads — typically ~10× speedup at 16 threads on aircraft-class
workloads.  macOS clang ships without OpenMP, so the macOS wheels
run serial (still faster than libspatialindex).

## Development

Source is formatted via `black` (Python) and `clang-format` (C++) — a
project-local `.clang-format` and `[tool.black]` block in
`pyproject.toml` pin the styles.

To run both formatters at once:

```
pip install pre-commit
pre-commit run --all-files
```

Or hand-run:

```
black boostree/ tests/ scripts/
clang-format -i src/*.cc benchmarks/*.cc
```

## Threading

The C++ extension declares itself compatible with PEP 703
free-threaded CPython (`py::mod_gil_not_used()`), and the batched
query methods (`nearest_v` / `intersection_v` / `knn` / `intersect`)
release the GIL so they parallelise across Python threads even on
the regular GIL build.

Each tree carries a `std::shared_mutex`: read methods take a shared
lock, mutators (`insert_point`, `delete_*`, `update_*`) take an
exclusive lock.  Concurrent reads run in parallel; reads block
during a write and vice versa.  No external synchronisation is
required, even on free-threaded CPython.

## Benchmarks

On 161 368 wall faces × 1 811 835 query points × k=8:

|                       | build   | k=8 query (1T) | k=8 query (16T) |
| --------------------- | ------- | -------------- | --------------- |
| `rtree` (PyPI)        | 1.10 s  | 80 s           | n/a (serial)    |
| `boostree`            | 0.03 s  | ~12 s          | ~1 s            |

## License

Boost Software License 1.0 (matches Boost.Geometry).
