header-only implementation of kd-tree.
following features are implemented.
- Nearest neighbor search
- k-Nearest neighbor search
- Spherical range search
- Graphviz dot language output
| filename | description |
|---|---|
include/kdtree.h |
header-only implementation of kd-tree |
include/kdtree_linear.h |
linear array version of include/kdtree.h. This is more efficient. |
examples/search.cpp |
visualization of neighbor search result |
examples/physics.cpp |
physics simulation of balls |
- C++ (>=20)
- CMake (>=3.12)
if you want to build examples, you also need followings.
- OpenGL 3.1
- SFML 2.5
in your CMakeLists.txt
add_subdirectory(<path-to-kdtree>)
target_link_libraries(<your-target> kdtree)// include kdtree
#include "kdtree/kdtree.h"
// setup points
std::vector<Point> points;
// populate points here...
// setup kdtree
kdtree::KdTree<Point> tree(points);
// build kdtree
tree.buildTree();
// nearest neighbor search
Point queryPoint = ...
int index_of_nearest = tree.searchNearest(queryPoint);
// k-nearest neighbor search
int k = 5;
std::vector<int> indices_of_k_nearest = tree.searchKNearest(queryPoint, k);
// spherical range search
float r = 1.5;
std::vector<int> indices_of_range = tree.sphericalRangeSearch(queryPoint, r);Note that Point must have following members.
T Point::operator[](unsigned int) const: element accessstatic unsigned int Point::dim: number of dimension
Run following command to get external libraries.
git submodule update --initThen, set cmake option KDTREE_EXAMPLES to On and build.
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release -DKDTREE_EXAMPLES=On ..
make
Collision detection with kd-tree.
generated dot file
digraph {
0->9 [label=0]
9->6 [label=1]
null60 [label="", shape="none"]
6->null60 [label=0]
null61 [label="", shape="none"]
6->null61 [label=0]
9->4 [label=1]
null40 [label="", shape="none"]
4->null40 [label=0]
4->3 [label=0]
null30 [label="", shape="none"]
3->null30 [label=1]
null31 [label="", shape="none"]
3->null31 [label=1]
0->5 [label=0]
5->7 [label=1]
null70 [label="", shape="none"]
7->null70 [label=0]
7->8 [label=0]
null80 [label="", shape="none"]
8->null80 [label=1]
null81 [label="", shape="none"]
8->null81 [label=1]
5->2 [label=1]
null20 [label="", shape="none"]
2->null20 [label=0]
2->1 [label=0]
null10 [label="", shape="none"]
1->null10 [label=1]
null11 [label="", shape="none"]
1->null11 [label=1]
}