K-nearest neighbors with KD-TREE in c ++

0

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);

}

    
asked by anonymous 07.05.2018 / 04:01

0 answers