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 74a2d93b63 spelling 2 weeks ago
bin libtool-update script 2 months ago
config this should not be a symlink 2 months ago
src spelling 3 weeks ago
.distignore don't use $(DESTDIR) in -rpath for executables ... 2 months ago
.gitattributes install bats 1.3.0 2 months ago
.gitignore add --enable-acceptance-tests option to configure 2 months ago
.gitlab-ci.yml correct dir 4 weeks ago spelling 2 weeks ago
LICENCE add licence 2 years ago
Makefile initial attempt at libtool 2 months ago fixing documentation, messages; bumped version 2 months ago
VERSION 1.0.6 2 months ago
aclocal.m4 initial attempt at libtool 2 months ago
configure 1.0.6 2 months ago 1.0.6 2 months ago
status.json spelling 2 weeks ago


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.


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


Quite standard:

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.

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

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

See ./configure --help for additional features.

OS-specific dependencies

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

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


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).