Flatbush (Java Port)

A high-performance, static R-tree spatial index for 2D rectangles, ported from the popular JavaScript Flatbush library.
This Java version is a close line-by-line port for maximum speed and minimal footprint. No external dependencies.

Features

• Bulk insertion of axis-aligned rectangles (or points).
• Hilbert-curve sorting for optimal packing.
• O(n) index construction time.
• Very fast rectangle-intersection queries.
• Efficient k-nearest-neighbors queries with optional distance limit and filtering.
• Primitive arrays only; zero GC churn during queries.
• All in a single small class (Flatbush.java).

Usage

Flatbush index = new Flatbush(1000); // number of items must be known up front

for (double[] r : rects) {
    index.add(r[0], r[1], r[2], r[3]); // minX, minY, maxX, maxY
}
index.finish(); // build the tree; no more adds after this

// ids of rectangles intersecting the query box (unordered)
int[] hits = index.search(qMinX, qMinY, qMaxX, qMaxY);

// 5 nearest neighbours to a point
int[] nearest = index.neighbors(x, y, 5);

// neighbours within a max distance, filtered by id
int[] close = index.neighbors(x, y, 10, 50.0, id -> id % 2 == 0);

// stream neighbours in distance order, stopping whenever you like
index.neighbors(x, y, (dist, id) -> dist < 100);

Ids returned by queries are the zero-based order in which items were added (also returned by add), so keep a parallel array or list of your objects and look them up by id. Alternatively, FlatBushIndex<T> wraps this for you:

FlatBushIndex<String> index = new FlatBushIndex<>(3);
index.add("a", 10, 10, 20, 20);
index.add("b", 15, 15, 25, 25);
index.add("c", 90, 90, 95, 95);
index.finish();

List<String> found = index.search(0, 0, 30, 30); // ["a", "b"]
List<String> nearest = index.neighbors(0, 0, 1);  // ["a"]

Once built, the index is immutable. search is safe to call from multiple threads; neighbors reuses an internal queue, so give each thread its own index (or synchronise) if you need concurrent k-NN queries.