libkdtree++ is an STL-like C++ template container implementation of
k-dimensional space sorting, using a kd-tree. It sports
a theoretically unlimited number of dimensions, and can store any data
structure. Provided the data structure, it provides
operator[0 - k-1] to
access the individual dimensional components (arrays,
do) and a
std::less implementation for the type of dimensional components.
It has support for custom allocators, implements iterators, and provides
standard find as well as range queries. It has amortised
O(lg n) time (
lg n) worst case) on most operations (insert/erase/find optimised) and
O(n) space, and also provides a means to rebalance and thus
optimise the tree.
The library is in a usable state, and increasingly likely to be bug-free.
libkdtree++ was written in 2004 by Martin F. Krafft. Paul Harris has made
some valuable contributions after its first release. Martin switched fields of
research in 2005 and never needed the code again, letting it rot. In 2007,
Sylvain Bougerel stepped up to take over maintenance. In 2008, Paul and Sylvain
released a stable version 0.7.0. In 2009 Paul took over the maintenance.
libkdtree++ is © 2004-2007 Martin F. Krafft. Parts of
are © 2004-2008 Paul Harris. Parts of the code are © 2007-2008 Sylvain Bougerel. Python wrapper is © 2008 Willi Richert.
It is released under the terms of the Artistic License
30 Dec 2008: Just in time to meet the “sometime this year” release date, 0.7.0 has been released. 0.6.3 had to be pulled because of various bugs which have now been resolved.
- I (Paul) decided to release as 0.7.0 as its been a long time since the last stable release (0.6.2). The 0.7 line will serve as a base for a stable kdtree, while new experimental API-breaking features are trialled in the next 0.8 series.
- Lots of bug fixes, some performance improvements, a Python wrapper and CMake support!
17 Nov 2008: Recently a whole lot of bug have been fixed in version 0.6.3 of the library. You can find a summary of the fixes in the Changelog. For short:
- you can now assign an existing tree to another tree without an ugly bug if your tree required parameters for the accessor,
- now you can finally use the reverse iterator,
- find() and erase() work properly based on the location given in argument,
- the project is compatible with MSVC2005
Credits for the patches and the new test files goes to Antibyte Scoopex, Sam Hayne, Martin Schreiber, Paul Harris and myself.
25 Nov 2007: fixed the reverse_iterator. Now it can be used. Moreover I’ve added some tarballs for those who do not have git.
24 Oct 2007: An update of the library is now available. That update features numerous of enhancements by Paul Harris:
const kdtreecan be searched
- findnearestif() enforce validation of a predicate
visit_within_range()walk the tree and calls
Visitor::operator()on template argument
<Visitor>for each node within the range
kdtree::value_typeby location and by calling
kdtree::value_type::operator==()(in case two different items have the same location
find_exact()will not return the wrong item)
num_dist_calcsfor debugging purpose plus additional improvements on erase and region intersection
Additionally, the library will not raise any warnings when compiled with the flags:
-Wall -pedantic -ansi
29 Sep 2007: Sylvain Bougerel spent some time cleaning up the code and build infrastructure of the code from Sourceforge, and I imported the results of his work to a git repository on git.debian.org today. Unfortunately, I had to give up the history because the GNU arch repository I had used in between was corrupted.
Getting the source
For now, please obtain the source directly from the git repository:
git clone git://git.debian.org/git/libkdtree/libkdtree.git
Alternatively you can get either of the tarball:
- libkdtree++-0.7.0.tar.bz2 (sha1sum)
- libkdtree++-0.7.0.tar.gz (sha1sum)
- or browse older version of the repository at https://alioth.debian.org/projects/libkdtree/
Commit messages are sent to this mailinglist, so if you like to receive emails when changes are commited, subscribe there.
You can also browse the code online.
A simple example/test
is included with the code. Its output (on
i386) is as follows:
meta node: 0x8053008 (0,0,0); parent: 0x8053028; left: 0x8053148; right: 0x8053108 nodes total: 10 dimensions: 3 0x8053028 (5,4,0); parent: 0x8053008; left: 0x8053048; right: 0x8053068 0x8053068 (7,6,9); parent: 0x8053028; left: 0x80530a8; right: 0x80530c8 0x80530c8 (5,7,0); parent: 0x8053068; left: 0; right: 0x8053108 0x8053108 (9,7,3); parent: 0x80530c8; left: 0; right: 0 0x80530a8 (8,0,5); parent: 0x8053068; left: 0; right: 0 0x8053048 (4,2,1); parent: 0x8053028; left: 0x8053148; right: 0x8053088 0x8053088 (2,2,1); parent: 0x8053048; left: 0; right: 0x80530e8 0x80530e8 (3,3,8); parent: 0x8053088; left: 0x8053128; right: 0 0x8053128 (2,2,6); parent: 0x80530e8; left: 0; right: 0 0x8053148 (2,0,6); parent: 0x8053048; left: 0; right: 0 meta node: 0x8053008 (0,0,0); parent: 0x8053148; left: 0x80530e8; right: 0x8053068 nodes total: 6 dimensions: 3 0x8053148 (7,6,9); parent: 0x8053008; left: 0x8053128; right: 0x8053068 0x8053068 (9,7,3); parent: 0x8053148; left: 0x8053108; right: 0 0x8053108 (8,0,5); parent: 0x8053068; left: 0; right: 0 0x8053128 (2,2,6); parent: 0x8053148; left: 0x80530e8; right: 0x80530a8 0x80530a8 (3,3,8); parent: 0x8053128; left: 0; right: 0 0x80530e8 (2,0,6); parent: 0x8053128; left: 0; right: 0 counted 1 nodes within range 3 of (5,4,3). found 1 nodes within range 3 of (5,4,3). (2,2,6) Nearest to (5,4,3): (2,2,6) Nearest to (10,10,2): (9,7,3) meta node: 0x8053008 (0,0,0); parent: 0x8053148; left: 0x80530e8; right: 0x8053068 nodes total: 6 dimensions: 3 0x8053148 (7,6,9); parent: 0x8053008; left: 0x8053128; right: 0x8053068 0x8053068 (9,7,3); parent: 0x8053148; left: 0x8053108; right: 0 0x8053108 (8,0,5); parent: 0x8053068; left: 0; right: 0 0x8053128 (2,2,6); parent: 0x8053148; left: 0x80530e8; right: 0x80530a8 0x80530a8 (3,3,8); parent: 0x8053128; left: 0; right: 0 0x80530e8 (2,0,6); parent: 0x8053128; left: 0; right: 0
We welcome any contributions in the form of patches. To submit a patch, please follow these guidelines. The procedure is roughly as follows:
First, the setup, which you only have to do once on each machine you work with:
# leave out --global if you want to set your identity only for libkdtree++ git config --global user.name 'your name' git config --global user.email 'firstname.lastname@example.org' # the next two are not needed but ensure that git does not send patches to # your own email address. git config sendemail.signedoffcc false git config sendemail.suppressfrom true git clone git://git.debian.org/git/libkdtree/libkdtree.git
To make changes to the code, bring your local clone up to date, create a throwaway branch and do your work on it.
git pull git checkout -b some-name-identifying-my-work # while not finished: # if resuming after a while, maybe update your branch: # git rebase master // edit files git add files git commit # end
After you’ve brought your change to a state where you want to submit it, please squash it into logical single commits. If you only made one change, then this will do:
git checkout -b temp-squash master git merge --squash some-name-identifying-my-work git commit // ... remove the "Squashed commit of the following:" leader git format-patch -M -s master // now inspect the files this created in $PWD // when you're ready to submit, do: git send-email <the patch files lying now in your current directory> --to email@example.com // check that it's okay when it arrives git send-email <the patch files lying now in your current directory> --to firstname.lastname@example.org
For multiple logical changes, cherry-pick or squash-merge every commit belonging to a change to the integration branch and then commit it. Also, read the git-send-email manpage in case you’re submitting multiple logical changes, in case you want to thread them.
The manpage also includes information about adding a prologue message explaining your patch, or how to insert it into an existing thread (in-reply-to).
Developers with write access to the repository may also push their changes, using the ssh transport instead of the git protocol. If you contribute a lot, we will gladly give you write access.
git clone git://git.debian.org/git/libkdtree/ikiwiki.git
Patches welcome. Or just hit the ‘Edit’ button at the top and make the changes through the web; it’s a wiki, after all!