DynamicKDTree.hpp

Go to the documentation of this file.

//
// Created by patrick on 4/11/19.
//
 
#ifndef LAS_VEGAS_DYNAMICKDTREE_HPP
#define LAS_VEGAS_DYNAMICKDTREE_HPP
 
namespace lvr2{
 
    template <typename BaseVecT>
    struct Node
    {
        BaseVecT point; // To store k dimensional point
        Index vH; //To store the belonging vertexHandle index
        Node<BaseVecT> *left, *right;
    };
 
    template <typename BaseVecT>
    class DynamicKDTree {
 
    private:
        Node<BaseVecT>* root;
        int k;
 
        struct Node<BaseVecT>* newNode(BaseVecT point, VertexHandle vH);
 
        Node<BaseVecT>* insertRec(Node<BaseVecT>* node, BaseVecT point, VertexHandle vH, unsigned int depth);
 
        Node<BaseVecT>* minNode(Node<BaseVecT>* x, Node<BaseVecT>* y, Node<BaseVecT>* z, int d);
 
        Node<BaseVecT>* findMinRec(Node<BaseVecT>* node, int d, unsigned depth);
 
        Node<BaseVecT> *findMin(Node<BaseVecT>* node, int d);
 
        bool arePointsSame(BaseVecT point1, BaseVecT point2)
        {
            return point1 == point2;
        }
 
        void copyPoint(BaseVecT& p1, BaseVecT& p2)
        {
            p1 = p2;
        }
 
        Node<BaseVecT>* deleteNodeRec(Node<BaseVecT>* node, BaseVecT point, int depth);
 
        int sizeRec(Node<BaseVecT>* node);
 
        std::pair<Index, float> findNearestRec(Node<BaseVecT>* node, BaseVecT point, int depth, Index minDist, float minDistSq, BaseVecT currentBest);
 
    public:
        void insert(BaseVecT point, VertexHandle vH);
 
        void deleteNode(BaseVecT point);
 
        int size();
 
        Index findNearest(BaseVecT point);
 
        explicit DynamicKDTree(int k) : k(k)
        {
            root = NULL;
        }
 
        //TODO
        ~DynamicKDTree() = default;
 
    };
}
 
#include "DynamicKDTree.tcc"
 
#endif //LAS_VEGAS_DYNAMICKDTREE_HPP