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

Asked

Viewed 124 times

0

I need to implement an algorithm to find the nearest k-neighbors to a certain point in the plane. Most of the material found on the internet be in English, accurate algorithm and working description I first implemented the point class 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 in:

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

}

  • 2

    No offense or anything. But stackoverflow is a place to ask questions ( ask no help for code implementation). And just as stated in this very important post https://meta.stackoverflow.com/questions/261592/how-much-research-effort-is-expected-of-stack-overflow-users you should search on your own for the answer / what you want. Only after you REALLY don’t get any results, you should come ask on stackoverflow.

  • And doubt it, my code is giving, and you can be sure that I have researched at least in 100 places, I have no idea to get implemented, I will come nights and night breaking my head with it

  • Where is your code that implements the algorithm?

  • my friends my code be posted(updated), if it will not help , do not criticize!

  • @Andreluiz, I understand your feeling, but here the people who help do it by their own free will. Help us by showing your algorithm implementation with minimal and complete code, so we can help you answer your questions.

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.