Skip to content

Latest commit

 

History

History
152 lines (114 loc) · 3.44 KB

README.md

File metadata and controls

152 lines (114 loc) · 3.44 KB
Raw

kdtree

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

Requirements

  • C++ (>=20)
  • CMake (>=3.12)

if you want to build examples, you also need followings.

How to integrate kdtree into your cmake project

in your CMakeLists.txt

add_subdirectory(<path-to-kdtree>)
target_link_libraries(<your-target> kdtree)

How to use kdtree in your source

// 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 access
  • static unsigned int Point::dim: number of dimension

How to build examples

Run following command to get external libraries.

git submodule update --init

Then, set cmake option KDTREE_EXAMPLES to On and build.

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release -DKDTREE_EXAMPLES=On ..
make

Gallery

Nearest Neighbor Search

Physics

Collision detection with kd-tree.

Graphviz dot language output

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]
}

Externals

References