Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations

Spatial is a generic header-only C++ library providing multi-dimensional in-memory containers, iterators and functionals. Spatial is a general purpose library with good overall performance thanks to its self-balancing k-d tree containers. Spatial makes it easy to search for nearest neighbors, orthogonal ranges, or perform ordering of objects in any number of dimensions.

Spatial's design borrows heavily from the STL, and strives to follow it's elegant interface; therefore Spatial's containers, iterators and functionals integrate well with the STL. Additionally, Spatial's self-balancing k-d tree-based containers, capable of object insertion and removal in fractional amortized time, prevent worst-case computational time on most operations.

Spatial was created with tracking analysis and real-time positioning in mind, but its good overall performance and its set of algorithms should make it as simple for anyone to do spatial analysis in their application as using STL's multiset or map containers.

Features Overview

A brief overview of Spatial's features is provided below:

  • Based on k-d trees which provide good overall performance for only 3 std::ptrdiff_t (and sometimes 1 extra std::size_t) of overhead per node
  • Sort objects along several dimensions that may be of different types
  • static (compile-time) or dynamic (run-time) determination of the number of dimensions
  • Policy-based rebalancing of the k-d tree, limiting worst-case performance, upon insertion and removal
  • Insertions in logarithmic amortized time, removals in fractional amortized time
  • Closely resemble the STL in design, with compatible containers and iterators
  • Iteration over orthogonal range with custom predicates and support for points or boxes
  • Iteration over neighbors, from nearest to furthest with custom metrics
  • Iteration over a single dimension, independantly from others
  • and more...

Spatial provides what is generally needed to get you started on simple spatial analysis. Check out Quick Starting Guide to get you started on using Spatial.

Getting the Source

ZIP packages are available at the Project Page on Sourceforge.

Packages on the Project Download Page on Sourceforge include the entire content of the source. Documentation files are only included in the * packages.

If you have a Git client and which to use this instead of the packages, you can clone the repository using the following command:

git clone git:// spatial

The above will only give you readonly access. If you wish to become a full-time contributor, check out Contributing.

Status of the Library

Spatial C++ Library's currently lacks of a proper documentation and set of examples. However the current library's API is considered stable since there are currently no foreseen development in plan that should cause it to change. Work is in progress to put the documentation on par with the source.

Spatial C++ Library is estimated by its author to be production-ready. The library is unit tested with each release, with unit tests covering more than 90% of it's current source code.

Spatial's unit test suite should compile without error or warning (even on high warning levels) and execute without errors on the following compilers:

  • GCC G++ 5.2 on x86_64 architectures only
  • GCC G++ 5.2 on x86_64 architectures only with C++11 support
  • Clang C++ 3.7 with libstdc++ on x86_64 architectures only
  • Clang C++ 3.7 with libstdc++ on x86_64 architectures only with C++11 support
  • Clang C++ 3.7 with libc++ on x86_64 architectures only
  • Microsoft Visual Studio 2010 on X64 architectures only

Spatial has not been tested on other compilers or other architectures. Any feedback in this regard is greatly appreciated.

History of the Library

Spatial C++ library was inspired from libkdtree++, and aims at providing a library that retains all the great benefits of libkdtree++ while broadening its horizons. It is through the informative feedback of its maintainers and its community that the design principles for this library have emerged.

Spatial, however, is a complete rewrite and shares none of its sources in common with libkdtree++.


Spatial C++ Library is provided under the term of the Boost license. Alternatively, see the file COPYING provided with your copy of the library.

Getting Support

You can ask for support on the general mailing list of the library:

To access feedback facilities, such as bug or feature requests, please refer to the Project Page on Sourceforge. If you wish to contribute to the library, check out Contributing.