Skip to content

alyst/SpatialIndexing.jl

master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
src
 
 
 
 
 
 
 
 
 
 
 
 

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