Home

Awesome

Flatbush for C++

Ubuntu Windows macOS CodeQL DevSkim flawfinder GitHub release (latest by date) Conan Center Vcpkg

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

As such, unit tests and benchmarks are virtually identical in order to provide a close comparison to the original.

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);
}

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

// can reuse existing builder
// call builder.clear() or keep adding items
builder.add({ box.minX, box.minY, box.maxX, box.maxY });
auto other = builder.finish();

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){ return id % 2 == 0; };
auto evenIds = index.search({40, 40, 60, 60}, filterEven);

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){ return id % 2 != 0; };
auto oddIds = index.neighbors({40, 60}, maxResults, maxDistance, filterOdd);

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 template != encoded type
auto other = FlatbushBuilder<double>::from(buffer.data(), buffer.size());
// or
auto other = FlatbushBuilder<double>::from(&buffer[0], buffer.size());

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.

Unit tests

CMake

mkdir build && cd build
cmake ..
make
ctest -C Release

Standalone

gcc test.cpp -lstdc++ -Wall -O2 -DFLATBUSH_SPAN -o test && ./test
clang++ -Wall -O2 -DFLATBUSH_SPAN -o test test.cpp && ./test
cl /EHsc /O2 /DFLATBUSH_SPAN test.cpp && .\test.exe

Performance

On a i7-11850H @ 2.50GHz, Win10 version 20H2 / Ubuntu 20.04.3 LTS

bench testclang 10.0.0gcc 9.3.0cl 14.29.30137.0
index 1000000 rectangles:93ms112ms124ms
1000 searches 10%:120ms131ms194ms
1000 searches 1%:21ms23ms26ms
1000 searches 0.01%:3ms3ms4ms
1000 searches of 100 neighbors:12ms12ms17ms
1 searches of 1000000 neighbors:80ms59ms61ms
100000 searches of 1 neighbors:297ms363ms503ms