I need to implement an algorithm to find the k-neighbors closest to a certain point in the plane. Most of the material found on the internet is in English, I need the algorithm and the description of the operation I first implemented the class point as below:
struct Point
{
int x;
int y;
Point(const int &coordx, const int &coordy)
{
x = coordx;
y = coordy;
}
int &operator[](int i) // lvalue
{
if(i == 0) return x;
else return y;
}
const int &operator[](int i) const // rvalue
{
if(i == 0) return x;
else return y;
}
bool operator==(const Point &right) const
{
if(this->x == right.x && this->y == right.y)
return true;
return false;
}
};
The class no:
class KdTreeNo
{
public:
KdTreeNo(Point key);
~KdTreeNo();
Point data;
KdTreeNo *left;
KdTreeNo *right;
};
and finally the KD-TREE class:
class KdTree
{
public:
KdTree(const int &_DIM);
~KdTree();
void insert( Point key) { insertAux(root, key, 0);}
void print() const { printAux(root,0);}
float distance( Point &a, Point &b)
{
float dx = a.x - b.x;
float dy = a.y - b.y;
return sqrt(dx*dx + dy*dy);
}
private:
int DIM;
KdTreeNo *root;
void insertAux( KdTreeNo *&ptr, Point key, int dim);
void printAux( KdTreeNo *ptr, int nivel) const ;
};
void KdTree :: NNAux (KdTreeNo * ptr, int dim, Point & query, float & bestDist) { if (query == ptr-> data) { bestDist = 0; return; } bestDist = distance (query, ptr-> data); if (ptr-> left == nullptr & & ptr- > right == nullptr) return;
if(query[dim] < ptr->data[dim])
NNAux(ptr->left, (dim + 1)%DIM, query,bestDist);
else
NNAux(ptr->right, (dim + 1)%DIM, query,bestDist);
}