SpatialIndexing.jl

Spatial data indexing in pure Julia (R*-trees etc)
Author alyst
Popularity
22 Stars
Updated Last
1 Year Ago
Started In
November 2018

SpatialIndexing.jl

Build Status codecov

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)

See also

Other Julia packages for spatial data:

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

Required Packages

No packages found.