spatial-trees is a set of dynamic index data structures for spatially-extended data.
Common Lisp
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.
.gitignore initial commit in NNS Nov 24, 2013
BUGS Add a bug entry about R* trees Dec 16, 2004
LICENCE
README.md updated the readme and api Nov 28, 2013
TODO documentation: api, readme... Nov 23, 2013
api.org readme Nov 28, 2013
basedefs.lisp Add (unused as yet) check-consistency generic function Nov 30, 2004
greene-trees.lisp Move all the tests into their own file, treated as static by the system Nov 23, 2004
nearest-search-test.lisp finally, removed tests on r* Dec 8, 2013
nearest-search.lisp bugfix: load some structures at the compile time. Dec 1, 2013
package.lisp merge guicho271828-nearest-neighbor-search Nov 25, 2013
r-trees.lisp Bounding Rectangle Nov 9, 2013
rectangles.lisp %intersect/1d-p Aug 24, 2014
rplus-trees.lisp fix a couple of style warnings in r+-trees Nov 30, 2004
rstar-trees.lisp Move all the tests into their own file, treated as static by the system Nov 23, 2004
spatial-tree-test.lisp finally, removed tests on r* Dec 7, 2013
spatial-tree-viz.lisp it is awkward to run a test each time vizualizer is invoked. Nov 24, 2013
spatial-trees-viz.asd it is awkward to run a test each time vizualizer is invoked. Nov 24, 2013
spatial-trees.asd renamed the testing system: spatial-trees-test -> spatial-trees.test Dec 1, 2013
spatial-trees.nns.asd
spatial-trees.nns.test.asd initial commit in NNS Nov 24, 2013
spatial-trees.test.asd renamed the testing system: spatial-trees-test -> spatial-trees.test Dec 1, 2013
tutorial.lisp added a tutorial Nov 24, 2013
x-trees.lisp X-trees now seem to work. Index building is very slow. Nov 30, 2004

README.md

This code was written by Christophe Rhodes, and the following description was taken from cliki.net.

spatial-trees

spatial-trees is a set of dynamic index data structures for spatially-extended data. The flavors provided are, as of the 0.1 release (on 2004-12-03):

  • R-trees, as in R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING, Antonin Guttman, Proc. ACM SIGMOD Int. Conf. on Management of Data, 1984.

  • Greene-trees, as in An Implementation and Performance Analysis of Spatial Data Access Methods, Diane Greene, Proc. 5th IEEE Int. Conf. on Data Engineering, 1989.

  • R-trees, as in The _R-tree: An Efficient and Robust Access Method for Points and Rectangles_, Beckmann, Kriegel, Schneider and Seeger, Proc. ACM Int. Conf. on Management of Data, 1990

  • X-trees, as in The X-tree: An Index Structure for High-Dimensional Data, Berchtold, Keim and Kriegel, Proc. 22th Int. Conf. on Very Large Databases, 1996

Future work planned includes performance enhancements, incorporation of more index structures, and some work on supporting more optimal indexing when the entire set of data is known at index creation time; for more details, see the TODO file in the binary distribution.

The code is licensed BSD-style, and is intended to be similar in spirit to Nathan Froyd's TREES Library.

Currently quicklisp-loadable.

Here are some instructions:

  • Read the API first
  • For Tutorial, see tutorial.lisp
  • For Testing, run (asdf:test-system :spatial-trees).
  • In order to test a visual inspector, run (asdf:load-system :spatial-trees-viz) and the mcclim-based visualizer will show up.