KD_Trees
Implementation of K-D tree in C++ programming language
Demonstration Image
What's in this repository anyway?
- This is a C++(PL) implementation of K-D Trees
-
- Implementation ensures the nearest neighbour search facilities :
- Nearest neighbor search
- K-nearest neighbor search
- Radius search
- A header file (custom). Library
How do we actually use the K-D Tree class?
- As you might have heard from the source above, the class included of the K-D Tree inputs a user-defined point type as its template parameter, a default parameter.
- The point you pass has to be put through the following constraints :
- Implementation of operator[] <= accessor to its coordinates.
- Static member variable DIM <= dimension of the input.
- Passing point cloud to KDTree constructor starts to build K-D Tree.
- After implementation of K-D Tree, you can use Nearest neighbor search functions.
Procedure :
You need to get CMake tools for generating the executable, you can download it from here OR, you can also use the CMake tools extension in Visual Studio, provided by Microsoft.
#include "kdtree.h"
// user-defined point type (inherits std::array in order to use operator[])
class MyPoint : public std::array<double, 2>
{
public:
// dimension of the Point
static const int DIM = 2;
// As you want
// ...
};
int main()
{
// generate point cloud
std::vector<MyPoint> points = ...;
// build k-d tree
kdt::KDTree<MyPoint> kdtree(points);
// K-nearest neighbor search (gets indices to neighbors)
int k = 10;
MyPoint query = ...;
std::vector<int> indices = kdtree.knnSearch(query, k);
return 0;
}
Requirement
- OpenCV (For running sample code)
Following is the sample code for the Built :
How to build ?
Go to command prompt and change the directory to your desired location for cloning the repository using the
cd <location>
command. After this procedure, stay in the command prompt and clone this repository, using the commands :
$ git clone https://github.com/DrCybernotix/KD_Trees.git
$ cd KD_Trees
$ mkdir build
$ cd build
$ cmake ../
$ make
How to run?
./kdtree [seed]
- seed
- Seed of rand() in generating random point cloud