I think that “number of brilliant-but-insane former graduate students who still live in the campus library” is one of the metrics that U.S. News & World Report uses when ranking physics departments.
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 C11 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 binary or 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
- Support for embedding the library within your application (rather than making the library a dependency), see these notes
- Permissive licence (MIT)
source
- Download the library source code: librtree-1.3.2.tar.gz
- The project's code is hosted on GitLab and Codeberg
- The original Guttman-Green code can be downloaded from Melinda Green's personal pages
- A Ruby gem with documentation at RubyDoc.info
- A Python package with documentation at Read the Docs
- An Octave Package with documentation on GitLab
