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 *_documented.zip 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://git.code.sf.net/p/spatial/code 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++.

Licensing

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: spati.nosp@m.al-m.nosp@m.ain@l.nosp@m.ists.nosp@m..sour.nosp@m.cefo.nosp@m.rge.n.nosp@m.et.

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.