/kdtree

A simple C++ kdtree implementation

Primary LanguageC++MIT LicenseMIT

Kdtree

Kdtree is a C++ implementation of a kdtree.

Description

  • Simple
  • Lightweight
  • Static Kdtree
  • Header only
  • Nearest neighbor search
  • k-Nearest neighbors search
  • Neighbors search within a radius

Documentation

The Kdtree needs to be provided a GetCoord function along with the object type and the dimension. The GetCoord function is meant to access the n-th coordinate of the objects.

Examples code

An example of code is provided in examples/.

The program generates some random 2D points and creates a Kdtree from them. It then generates a random 2D point and searches for its nearest neighbors and its neighbors within a radius.

How to build

$ git clone https://github.com/tle-huu/kdtree.git
$ cd kdtree
$ mkdir build
$ cd build
$ cmake ..
$ make

How to run

$ cd build/examples
$ ./find_nn
$ python3 draw.py
  • find_nn
    • Generate random 2D points and create a kdtree.
    • Generate a random point whose neighbors we want to find
    • Dump Kdtree points, the random point, and its neighbors in a file 'kdtree.txt'
  • draw.py
    • Parse 'kdtree.txt' and plot the points and found neighbors

License

Distributed under the MIT License.