kdtree module for C++
- Copy
kdtree.hpp
andnode.hpp
to your project. - Write
#include "kdtree.hpp"
in your code.
This module uses namespace kdtree
.
Write using namespace kdtree;
if necessary.
kdtree
: A class having a pointer to the root node of the tree.node
: A class representing a node of the tree.
Generally you don't have to create a node directly, but it might be good to know how to create a node and access to its data.
node
is a template class and you can use any classes having the member x
and y
.
node<cv::Point> *node = new node<cv::Point>(cv::Point(10, 0));
The member point
represents the point of the node.
cout << node->point << endl; // [10, 0]
Read node.hpp
if you want to know about other methods and member variables.
kdtree
is a template class and you can use any classes having the member x
and y
.
Following example uses cv::Point
of OpenCV as a point of the tree.
vector<cv::Point> points = {
cv::Point(10, 0),
cv::Point(20, 0),
cv::Point(40, 0),
cv::Point(80, 0),
cv::Point(160, 0)
};
kdtree<cv::Point> *tree = new kdtree<cv::Point>(points);
Read kdtree.hpp
if you want to know about other methods and member variables.
Just delete
the instance of the tree.
delete tree;
Use nearest()
.
In this example the result is the node having cv::Point(40, 0)
.
node<cv::Point> *nearest_neighbor = tree->nearest(cv::Point(50, 0));
In this example the result is the node having cv::Point(80, 0)
.
node<cv::Point> *nearest_neighbor = tree->nearest(cv::Point(80, 0));
Use radius_nearest()
.
vector<node<cv::Point> *> neighbors = tree->radius_nearest(cv::Point(70, 0), 100);
In this example the result is {(80, 0), (40, 0), (20, 0), (10, 0), (160, 0)}
.
Use k_nearest()
.
vector<node<cv::Point> *> neighbors = tree->k_nearest(cv::Point(70, 0), 5);
In this example the result is {(80, 0), (40, 0), (20, 0), (10, 0), (160, 0)}
.
main.cpp
includes primitive unit tests with assert
.
You can run the test by using make clean run
.
kdtree is released under the MIT License, see LICENSE.txt.