rtree

<a href="https://github.com/davidmoten/rtree/actions/workflows/ci.yml"><img src="https://github.com/davidmoten/rtree/actions/workflows/ci.yml/badge.svg"/></a><br/> <br/> <br/>

In-memory immutable 2D R-tree implementation in java using RxJava Observables for reactive processing of search results.

Status: released to Maven Central

Note that the next version (without a reactive API and without serialization) is at rtree2.

An R-tree is a commonly used spatial index.

This was fun to make, has an elegant concise algorithm, is thread-safe, fast, and reasonably memory efficient (uses structural sharing).

The algorithm to achieve immutability is cute. For insertion/deletion it involves recursion down to the required leaf node then recursion back up to replace the parent nodes up to the root. The guts of it is in Leaf.java and NonLeaf.java.

Backpressure support required some complexity because effectively a bookmark needed to be kept for a position in the tree and returned to later to continue traversal. An immutable stack containing the node and child index of the path nodes came to the rescue here and recursion was abandoned in favour of looping to prevent stack overflow (unfortunately java doesn't support tail recursion!).

Maven site reports are here including javadoc.

Features

• immutable R-tree suitable for concurrency
• Guttman's heuristics (Quadratic splitter) (paper)
• R*-tree heuristics (paper)
• Customizable splitter and selector
• 10x faster index creation with STR bulk loading (paper).
• search returns Observable
• search is cancelled by unsubscription
• search is O(log(n)) on average
• insert, delete are O(n) worst case
• all search methods return lazy-evaluated streams offering efficiency and flexibility of functional style including functional composition and concurrency
• balanced delete
• uses structural sharing
• supports backpressure
• JMH benchmarks
• visualizer included
• serialization using FlatBuffers
• high unit test code coverage
• R*-tree performs 900,000 searches/second returning 22 entries from a tree of 38,377 Greek earthquake locations on i7-920@2.67Ghz (maxChildren=4, minChildren=1). Insert at 240,000 entries per second.
• requires java 1.6 or later

Number of points = 1000, max children per node 8:

| Quadratic split | R*-tree split | STR bulk loaded | | :-------------: | :-----------: | :-----------: | | <img src="src/docs/quad-1000-8.png?raw=true" /> | <img src="src/docs/star-1000-8.png?raw=true" /> | <img src="src/docs/str-1000-8.png?raw=true" /> |

Notice that there is little overlap in the R*-tree split compared to the Quadratic split. This should provide better search performance (and in general benchmarks show this).

STR bulk loaded R-tree has a bit more overlap than R*-tree, which affects the search performance at some extent.

Getting started

Add this maven dependency to your pom.xml:

<dependency>
  <groupId>com.github.davidmoten</groupId>
  <artifactId>rtree</artifactId>
  <version>VERSION_HERE</version>
</dependency>

Instantiate an R-Tree

Use the static builder methods on the RTree class:

// create an R-tree using Quadratic split with max
// children per node 4, min children 2 (the threshold
// at which members are redistributed)
RTree<String, Geometry> tree = RTree.create();

You can specify a few parameters to the builder, including minChildren, maxChildren, splitter, selector:

RTree<String, Geometry> tree = RTree.minChildren(3).maxChildren(6).create();

Geometries

The following geometries are supported for insertion in an RTree:

• Rectangle
• Point
• Circle
• Line

Generic typing

If for instance you know that the entry geometry is always Point then create an RTree specifying that generic type to gain more type safety:

RTree<String, Point> tree = RTree.create();

R*-tree

If you'd like an R*-tree (which uses a topological splitter on minimal margin, overlap area and area and a selector combination of minimal area increase, minimal overlap, and area):

RTree<String, Geometry> tree = RTree.star().maxChildren(6).create();

See benchmarks below for some of the performance differences.

Add items to the R-tree

When you add an item to the R-tree you need to provide a geometry that represents the 2D physical location or extension of the item. The Geometries builder provides these factory methods:

• Geometries.rectangle
• Geometries.circle
• Geometries.point
• Geometries.line (requires jts-core dependency)

To add an item to an R-tree:

RTree<T,Geometry> tree = RTree.create();
tree = tree.add(item, Geometries.point(10,20));

or

tree = tree.add(Entries.entry(item, Geometries.point(10,20));

Important note: being an immutable data structure, calling tree.add(item, geometry) does nothing to tree, it returns a new RTree containing the addition. Make sure you use the result of the add!

Remove an item in the R-tree

To remove an item from an R-tree, you need to match the item and its geometry:

tree = tree.delete(item, Geometries.point(10,20));

or

tree = tree.delete(entry);

Important note: being an immutable data structure, calling tree.delete(item, geometry) does nothing to tree, it returns a new RTree without the deleted item. Make sure you use the result of the delete!

Geospatial geometries (lats and longs)

To handle wraparounds of longitude values on the earth (180/-180 boundary trickiness) there are special factory methods in the Geometries class. If you want to do geospatial searches then you should use these methods to build Points and Rectangles:

Point point = Geometries.pointGeographic(lon, lat);
Rectangle rectangle = Geometries.rectangleGeographic(lon1, lat1, lon2, lat2);

Under the covers these methods normalize the longitude value to be in the interval [-180, 180) and for rectangles the rightmost longitude has 360 added to it if it is less than the leftmost longitude.

Custom geometries

You can also write your own implementation of Geometry. An implementation of Geometry needs to specify methods to:

• check intersection with a rectangle (you can reuse the distance method here if you want but it might affect performance)
• provide a minimum bounding rectangle
• implement equals and hashCode for consistent equality checking
• measure distance to a rectangle (0 means they intersect). Note that this method is only used for search within a distance so implementing this method is optional. If you don't want to implement this method just throw a RuntimeException.

For the R-tree to be well-behaved, the distance function if implemented needs to satisfy these properties:

• distance(r) >= 0 for all rectangles r
• if rectangle r1 contains r2 then distance(r1)<=distance(r2)
• distance(r) = 0 if and only if the geometry intersects the rectangle r

Searching

The advantage of an R-tree is the ability to search for items in a region reasonably quickly. On average search is O(log(n)) but worst case is O(n).

Search methods return Observable sequences:

Observable<Entry<T, Geometry>> results =
    tree.search(Geometries.rectangle(0,0,2,2));

or search for items within a distance from the given geometry:

Observable<Entry<T, Geometry>> results =
    tree.search(Geometries.rectangle(0,0,2,2),5.0);

To return all entries from an R-tree:

Observable<Entry<T, Geometry>> results = tree.entries();

Search with a custom geometry

Suppose you make a custom geometry like Polygon and you want to search an RTree<String,Point> for points inside the polygon. This is how you do it:

RTree<String, Point> tree = RTree.create();
Func2<Point, Polygon, Boolean> pointInPolygon = ...
Polygon polygon = ...
...
entries = tree.search(polygon, pointInPolygon);

The key is that you need to supply the ```intersec