Awesome

SpatialIndexing.jl

Documentation:

SpatialIndexing package provides the tools for efficient in-memory indexing of spatial data in Julia.

Installation

using Pkg; Pkg.add("SpatialIndexing")

from Julia REPL.

Features

R-tree

R-tree organizes data into hierarchical structure and ensures that:

minimal bounding rectangles (MBRs) of the nodes (rectangles that encompass all data elements in the subtree) stay compact,
MBRs of the nodes from the same R-tree level have minimal overlap with each other.

The key benefit of R-tree is its ability to rebalance itself and maintain efficient structure while handling dynamic data (massive insertions and deletions).

SpatialIndexing provides RTree type that supports:

different R-tree variants (classic R-tree, R*-tree, linear and quadratic node splits)
insert!(tree, item), delete!(tree, item) for element-wise insertion and deletion
bulk-loading of data using Overlap-minimizing Top-down (OMT) approach (load!(tree, data))
subtract!(tree, reg) for removing data within specified region reg
findfirst(tree, reg, [id]), contained_in(tree, reg) and intersects_with(tree, reg) spatial queries

Simple Spatial Index

SimpleSpatialIndex stores all data elements in a vector. So, while insertion of new data takes constant time, the time of spatial searches grows linearly with the number of elements. This spatial index is intended as a reference implementation for benchmarking and not recommended for production usage.

TODO

Usage

TODO

examples folder contains spiral.jl and pareto.jl examples of using R-tree for storing spatial data.

R*-tree of 10000 random points (sequential insertions)

R*-tree of 3D Pareto Front (1233 of 100000 points; bulk-load)

References

A.Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching” Proc. 1984 ACM-SIGMOD Conference on Management of Data (1985), pp.47-57.
N. Beckmann, H.P. Kriegel, R. Schneider, B. Seeger, "The R*-tree: an efficient and robust access method for points and rectangles" Proc. 1990 ACM SIGMOD international conference on Management of data (1990), p.322
T. Lee and S. Lee, "OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree", CAiSE Short Paper Proceedings (2003) paper