The Guttman-Green R-tree spatial indexing algorithm, as a library
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 
J.J. Green 4355bb8b0d rtree-eps output now has a title 1 week ago
bin better names for the helper scripts 1 week ago
config better names for the helper scripts 1 week ago
src rtree-eps output now has a title 1 week ago
.distignore added .gitattributes to .distignore 7 months ago
.gitattributes git attributes includes rtree-query 1 week ago
.gitignore update gitignore 1 month ago
.gitlab-ci.yml rename configure --disable options ... 5 months ago
CHANGELOG.md Changelog, revert version artefacts to 0.9.3 1 week ago
LICENCE add licence 1 year ago
Makefile better names for the helper scripts 1 week ago
README.md update Changelog, README 1 month ago
VERSION Changelog, revert version artefacts to 0.9.3 1 week ago
aclocal.m4 move build-auxillary files in config/ ... 3 months ago
configure Changelog, revert version artefacts to 0.9.3 1 week ago
configure.ac Changelog, revert version artefacts to 0.9.3 1 week ago
status.json rtree-eps output now has a title 1 week ago

README.md

librtree

Implementation of the R-tree algorithm by A. Guttman, updated by Melinda Green. Retrieved from (1), July 2019. This rather old code (Green reports updating it to ANSI C) has been rewritten in C11 with an extensive test-suite to make a small, reasonably portable self-contained library. For use in smaller projects.

For documentation and stable releases, see the project homepage.

See (2), (3) for a similar developments in C++.

Features

The same underlying algorithms are implemented, and we have some features which seem desirable for a modern library:

  • Re-entrant, no global variables at all
  • Dimension set at run-time rather than compile-time
  • Extensive test-suite (with CUnit), used for CI (4)
  • Serialisation to/from custom binary format or JSON
  • Output to PostScript in the dimension-two case
  • Builds a 100,000 rectangle tree in around a third of a second

Status

This code is beta and the features planned for version 1.0 have been implemented.

Building

Quite standard:

./configure
make
sudo make install

If you do not have the Jansson library (or do not want JSON support) add the --disable-json option to the configure. Similarly, if you do not have libcsv (or do not want CSV support) pass the --disable-csv option.

To run the test-suite (which requires the CUnit library)

./configure --enable-unit-tests
make
make test

See ./configure --help for additional features.

OS-specific dependencies

Debian and derivatives (Ubuntu, Mint, ...)

  • build: libjansson-dev, libcsv-dev
  • test: libcunit1-dev, valgrind, ghostscript
  • develop: clang-tools, cppcheck, gengetopt, xsltproc, jq, cloc

Licence

The licence of the original files, according to (1), is that

You're completely free to use them for any purpose whatsoever. All I ask is that if you find one to be particularly valuable, then consider sending feedback.

Given this, I have released the rewrite under the MIT licence (see the file LICENCE).