librtree

An R-tree is a spatial data index which allows one to perform fast queries as to which of a potentially huge collection of rectangles (or higher dimensional cuboids) intersect a given rectangle. R-trees were introduced by A. Guttman in 1984 in the seminal paper R-Trees: A Dynamic Index Structure for Spatial Searching (pdf).

The librtree package is a C99 library based on the original implementation by Guttman, later extended by Melinda Green. We retain the overall design (in particular, the idea that the immediate children of a node be stored in the same page of memory), but make extensive changes to the implementation.

features

  • No global state at all, multiple threads can query the same R-tree simultaneously
  • The dimension of the R-tree is set at run-time (when the tree is built) rather than at compile-time
  • Build R-trees from a simple CSV format, dump them to JSON
  • Several utilities created with the library to build, dump and plot R-trees, useful in themselves and as examples of usage of the library
  • Extensive test-suite including unit-tests (with CUnit), memory checking (valgrind) and code analysis (clang's scan-build) run against every push to the project's repository
  • Permissive licence (MIT)

source

example R-tree