Flatbush for C++

A C++ adaptation of the great Flatbush JS library which implements a packed Hilbert R-tree algorithm.

As such, unit tests and benchmarks are largely based on the original source in order to provide a close comparison.

Acknowledgement

A very fast static spatial index for 2D points and rectangles in JavaScript by Vladimir Agafonkin, licensed under ISC

Usage

Create and build the index

using namespace flatbush;

// initialize the builder
FlatbushBuilder<double> builder;
// ... or preallocate buffer for 1000 items 
FlatbushBuilder<double> builder(1000);

// fill it with 1000 rectangles
for (const auto& box : boxes) {
    builder.add(box);
}

// points are indexed as zero-area boxes
builder.add(Point<double>{10, 20});

// perform the indexing
auto index = builder.finish();

// inspect the total extent of all indexed items without copying it
const auto& bounds = index.bounds();

finish() transfers the accumulated boxes into the index and resets the builder, which can then be filled again to build another independent index.

Searching a bounding box

// make a bounding box query
Box<double> boundingBox{40, 40, 60, 60};
auto foundIds = index.search(boundingBox);

// make a bounding box query using a filter function 
auto filterEven = [](size_t id, const Box<double>&){ return id % 2 == 0; };
auto evenIds = index.search({40, 40, 60, 60}, filterEven);

// stop after 100 accepted matches
auto firstEvenIds = index.search(boundingBox, filterEven, 100);

An omitted limit returns all matches; zero returns none. Results follow tree traversal order.

Filters and distance callbacks must be callable through a const reference.

Searching for nearest neighbors

// make a k-nearest-neighbors query
Point<double> targetPoint{40, 60};
auto neighborIds = index.neighbors(targetPoint);

// make a k-nearest-neighbors query with a maximum result threshold
auto neighborIds = index.neighbors({40, 60}, maxResults);

// make a k-nearest-neighbors query with a maximum result threshold and limit the distance
auto neighborIds = index.neighbors(targetPoint, maxResults, maxDistance);

// make a k-nearest-neighbors query using a filter function
auto filterOdd = [](size_t id, const Box<double>&){ return id % 2 != 0; };
auto oddIds = index.neighbors({40, 60}, maxResults, maxDistance, filterOdd);

maxDistance may be infinite, in which case no candidates are pruned by distance. A zero maxDistance searches for boxes containing or touching the query point.

Searching for nearest neighbors with a custom metric

By default, neighbors ranks and prunes on the planar Euclidean distance and maxDistance is expressed in index units. Passing a distance callback replaces that metric, in which case maxDistance is compared directly against whatever the callback returns.

// e.g. a great-circle metric for a lon/lat index, with maxDistance then given in metres
auto haversine = [](const Point<double>& point, const Box<double>& box) -> double {
    return distanceToBoxInMetres(point, box);
};
auto nearbyIds = index.neighbors({13.4, 52.5}, 10, 5000.0, {}, haversine);

The callback must return a lower bound of the distance from the point to any point inside the box, otherwise the traversal prunes and orders on a value it cannot trust. Note that it is invoked once per visited node box, so it bypasses the SIMD path used by the built-in metric.

Reconstruct from raw data

// get the view to the raw array buffer
auto buffer = index.data();

// then pass the underlying data, specifying the template type
// NOTE: an exception will be thrown if the template is incompatible with the encoded type
auto other = FlatbushBuilder<double>::from(buffer.data(), buffer.size());
// or, move the source vector into the builder
auto vector = std::vector<uint8_t>{buffer.begin(), buffer.end()};
auto other = FlatbushBuilder<double>::from(std::move(vector));

FlatbushBuilder<uint8_t> also accepts indexes encoded by the JavaScript library with Uint8ClampedArray, since clamping affects writes but not the serialized byte layout.

Reconstruct without copying

fromView builds the index directly on top of bytes it does not own, so nothing is copied. The buffer stays the caller's responsibility and must outlive the index and remain unchanged, which makes this the right fit for a memory mapping or a long-lived buffer shared between several indices.

// the index reads these bytes in place; `storage` must outlive `view` and remain unchanged
auto storage = std::vector<uint8_t>{buffer.begin(), buffer.end()};
auto bytes = span<const uint8_t>{storage.data(), storage.size()};
auto view = FlatbushBuilder<double>::fromView(bytes);

// several indices can share one buffer
auto second = FlatbushBuilder<double>::fromView(bytes);

Because the boxes are read in place, the buffer must be suitably aligned; an exception is thrown otherwise. isView() reports whether an index borrows its bytes rather than owning them.

Compiling

This is a single header library with the aim to support C++11 and up.

If the target compiler does not have support for C++20 features, namely the <span> header, a minimalistic implementation is available if FLATBUSH_SPAN flag is defined.

SIMD Optimizations

The library automatically detects and uses SIMD instructions for improved performance. You can control the SIMD level with the following flags:

ISA Level	GCC/Clang	MSVC
SSE2 (default on x64)	-msse2	/arch:SSE2
SSE3	-msse3	N/A
SSE4	-msse4	N/A
AVX	-mavx	/arch:AVX
AVX2	-mavx2	/arch:AVX2
AVX512	-mavx512f -mavx512dq -mavx512vl	/arch:AVX512

Unit tests

(cmake -B build/tests -DWITH_TESTS=ON && cmake --build build/tests -j $(nproc) && ./build/tests/unit_test)

Bench tests

(cmake -B build/bench -DWITH_BENCHMARKS=ON && cmake --build build/bench -j $(nproc) && ./build/bench/bench_test)

Fuzz tests

(cmake -B build/fuzz -DWITH_FUZZING=ON -DFUZZTEST_FUZZING_MODE=ON && cmake --build build/fuzz -j $(nproc) && ./build/fuzz/fuzz_test)

Performance

On an i7-1185G7 @ 3.00GHz, Win11 version 25H2 / Ubuntu 24.04.2 LTS

bench test	clang 18.1.3	gcc 13.3.0	cl 19.29.30159
index 1000000 rectangles:	55ms	59ms	72ms
1000 searches 10%:	79ms	80ms	91ms
1000 searches 1%:	17ms	18ms	18ms
1000 searches 0.01%:	2ms	2ms	2ms
1000 searches of 100 neighbors:	11ms	11ms	12ms
1 searches of 1000000 neighbors:	88ms	86ms	63ms
100000 searches of 1 neighbors:	152ms	150ms	168ms

Runner benchmarks over time for gcc and clang