RTree

RTree is a Java class that implements an R-tree spatial index for indexing rectangles and querying intersections between indexed rectangles and a given query rectangle. This implementation is especially suited for large datasets, where creating a Java object for each indexed spatial object is not an option.

All indexed rectangles are stored in two int[] arrays, which makes them easy to persist (for example, to a file) and memory efficient.

Geometric features (streets, parks, etc.) can be inserted into the RTree using their bounding rectangles. Once indexed, the RTree can be queried to find all objects that intersect with a given query rectangle.

The RTree has two possible states. The default state is read/write mode, where you can insert new rectangles and perform queries. The second state is compact mode, which is read only. In compact mode you cannot insert new objects, but the structure is more memory efficient and produces a smaller file when stored on disk.

Global rectangle:

The global rectangle defines the global minimum and maximum coordinates of all objects stored in the RTree. Coordinates outside these limits are clipped when new objects are added.

The global rectangle is defined at the beginning of the RTree.java class. By default it is prepared for geographic coordinates (-180, 180) and (-90, 90), multiplied by one million and stored as integers.

final static public int GLOBAL_MIN_X = -180000000;
final static public int GLOBAL_MIN_Y = -90000000;
final static public int GLOBAL_MAX_X = 180000000;
final static public int GLOBAL_MAX_Y = 90000000;

API:

public RTree(int maxRectCount, int maxObjCount); Constructor that allocates the initial capacity for indexing tiles and objects. The RTree automatically increases the size of its internal arrays when needed, so you can start with values like (10000, 100000).

public RTree(int[] rectsInp, int[] objsInp, boolean compactReadOnly); Constructor for an RTree loaded from a binary file. The binary file is read into the rectsInp and objsInp arrays. The compactReadOnly parameter specifies whether the RTree was stored in compact mode or default mode.

public int[] getRectArr(); public int getRectCount(); public int[] getObjArr(); public int getObjCount(); These methods return the internal arrays and their counts. They can be used to persist the RTree instance to disk. Later, the arrays can be loaded and passed to the appropriate constructor to recreate the RTree.

public void turnToCompactMode() Turns the RTree into read-only compact mode. After switching to compact mode, no new rectangles can be added and only queries are allowed. In compact mode the allocated arrays are smaller.

This mode is useful when all objects are added during an initial build phase and only queries are needed afterward.

public void addObj(int id, int minX, int minY, int maxX, int maxY) Adds a single rectangle, identified by id, to the RTree. The rectangle is defined by its minimum and maximum coordinates.

All coordinates are integers. For geographic latitude and longitude values, multiply coordinates by 1,000,000. All coordinates must lie within the global rectangle.

public ArrayList<Integer> getIntersectingObjs(int minX, int minY, int maxX, int maxY, boolean removeDuplicates) Returns IDs of all objects that intersect or overlap the given query rectangle.

If removeDuplicates is true, duplicate IDs are removed by the RTree. If false, handling of duplicates is left to the caller.