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 1ab859a3b6 profiles for 1.0.7 1 week ago
bin bats-version script 2 months ago
config bats-version script 2 months ago
src profiles for 1.0.7 1 week ago
.distignore don't use $(DESTDIR) in -rpath for executables ... 6 months ago
.gitattributes mark aclocal.m4 as generated 3 months ago
.gitignore add --enable-acceptance-tests option to configure 6 months ago
.gitlab-ci.yml add xsltproc as a CI dependency 2 months ago 1.0.7 1 week ago
LICENCE add licence 2 years ago
Makefile initial attempt at libtool 7 months ago move shellchec to list of test tools 3 months ago
VERSION 1.0.7 1 week ago
aclocal.m4 initial attempt at libtool 7 months ago
configure 1.0.7 1 week ago 1.0.7 1 week ago
status.json profiles for 1.0.7 1 week 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, shellcheck
  • 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).