//---------------------------------------------------------------------- // File: kd_tree.h // Programmer: Sunil Arya and David Mount // Description: Declarations for standard kd-tree routines // Last modified: 05/03/05 (Version 1.1) //---------------------------------------------------------------------- // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and // David Mount. All Rights Reserved. // // This software and related documentation is part of the Approximate // Nearest Neighbor Library (ANN). This software is provided under // the provisions of the Lesser GNU Public License (LGPL). See the // file ../ReadMe.txt for further information. // // The University of Maryland (U.M.) and the authors make no // representations about the suitability or fitness of this software for // any purpose. It is provided "as is" without express or implied // warranty. //---------------------------------------------------------------------- // History: // Revision 0.1 03/04/98 // Initial release // Revision 1.1 05/03/05 // Added fixed radius kNN search // -------------------------------------------------------------------- // 2015 - modified by A. Nigmetov to support deletion of points //---------------------------------------------------------------------- #ifndef ANN_kd_tree_H #define ANN_kd_tree_H #include // for std::pair #include // all ANN includes #include "def_debug_bt.h" using namespace std; // make std:: available namespace geom_bt { //---------------------------------------------------------------------- // Generic kd-tree node // // Nodes in kd-trees are of two types, splitting nodes which contain // splitting information (a splitting hyperplane orthogonal to one // of the coordinate axes) and leaf nodes which contain point // information (an array of points stored in a bucket). This is // handled by making a generic class kd_node, which is essentially an // empty shell, and then deriving the leaf and splitting nodes from // this. //---------------------------------------------------------------------- //class ANNkd_node; class ANNkd_split; //typedef std::pair ANNreplaceSearchRes; class ANNkd_node{ // generic kd-tree node (empty shell) protected: int actual_num_points; // ANNkd_split* parent; public: ANNkd_split* getParent() const { return parent; } void setParent(ANNkd_split* par) { parent = par; } int getNumPoints() const { return actual_num_points; } void setNumPoints(int n) { assert(n >=0 ); actual_num_points = n; } void decNumPoints() { assert(actual_num_points > 0); actual_num_points--; } virtual ~ANNkd_node() {} // virtual distroyer virtual void ann_search(ANNdist) = 0; // tree search virtual void ann_pri_search(ANNdist) = 0; // priority search virtual void ann_FR_search(ANNdist) = 0; // fixed-radius search virtual void getStats( // get tree statistics int dim, // dimension of space ANNkdStats &st, // statistics ANNorthRect &bnd_box) = 0; // bounding box // print node virtual void print(int level, ostream &out) = 0; #ifndef FOR_R_TDA virtual void dump(ostream &out) = 0; // dump node #endif friend class ANNkd_tree; // allow kd-tree to access us //////////////////////////////////////////////////////////////////////// // deletion virtual void delete_point(const int point_idx) {} // range search virtual void range_search(const ANNorthRect& region, // query region int ANNkdDim, // dimension of points, ANNpointArray ANNkdPts, // array of points ANNorthRect& bnd_box, // bounding box of the current node, // comes precomputed from the caller std::vector& pointIdices) {} // indices of points are returned in this vector virtual void range_search_add(std::vector& pointIdices) {} // add all points to pointIdices }; //---------------------------------------------------------------------- // kd-splitting function: // kd_splitter is a pointer to a splitting routine for preprocessing. // Different splitting procedures result in different strategies // for building the tree. //---------------------------------------------------------------------- typedef void (*ANNkd_splitter)( // splitting routine for kd-trees ANNpointArray pa, // point array (unaltered) ANNidxArray pidx, // point indices (permuted on return) const ANNorthRect &bnds, // bounding rectangle for cell int n, // number of points int dim, // dimension of space int &cut_dim, // cutting dimension (returned) ANNcoord &cut_val, // cutting value (returned) int &n_lo); // num of points on low side (returned) //---------------------------------------------------------------------- // Leaf kd-tree node // Leaf nodes of the kd-tree store the set of points associated // with this bucket, stored as an array of point indices. These // are indices in the array points, which resides with the // root of the kd-tree. We also store the number of points // that reside in this bucket. //---------------------------------------------------------------------- class ANNkd_leaf: public ANNkd_node // leaf node for kd-tree { int n_pts; ANNidxArray bkt; // bucket of points public: ANNkd_leaf( // constructor int n, // number of points ANNidxArray b) : // bucket n_pts(n), bkt(b) { setNumPoints(n); parent = NULL; } ~ANNkd_leaf() { } // destructor (none) virtual void getStats( // get tree statistics int dim, // dimension of space ANNkdStats &st, // statistics ANNorthRect &bnd_box); // bounding box virtual void print(int level, ostream &out);// print node #ifndef FOR_R_TDA virtual void dump(ostream &out); // dump node #endif virtual void ann_search(ANNdist); // standard search virtual void ann_pri_search(ANNdist); // priority search virtual void ann_FR_search(ANNdist); // fixed-radius search // deletion void delete_point(const int point_idx, const bool killYourself); // range search virtual void range_search(const ANNorthRect& region, // query region int ANNkdDim, // dimension of points, ANNpointArray ANNkdPts, // array of points ANNorthRect& bnd_box, // bounding box of the current node, // comes precomputed from the caller std::vector& pointIdices); // indices of points are returned in this vector virtual void range_search_add(std::vector& pointIdices); // add all points to pointIdices }; //---------------------------------------------------------------------- // KD_TRIVIAL is a special pointer to an empty leaf node. Since // some splitting rules generate many (more than 50%) trivial // leaves, we use this one shared node to save space. // // The pointer is initialized to NULL, but whenever a kd-tree is // created, we allocate this node, if it has not already been // allocated. This node is *never* deallocated, so it produces // a small memory leak. //---------------------------------------------------------------------- extern ANNkd_leaf *KD_TRIVIAL; // trivial (empty) leaf node //---------------------------------------------------------------------- // kd-tree splitting node. // Splitting nodes contain a cutting dimension and a cutting value. // These indicate the axis-parellel plane which subdivide the // box for this node. The extent of the bounding box along the // cutting dimension is maintained (this is used to speed up point // to box distance calculations) [we do not store the entire bounding // box since this may be wasteful of space in high dimensions]. // We also store pointers to the 2 children. //---------------------------------------------------------------------- class ANNkd_split : public ANNkd_node // splitting node of a kd-tree { int cut_dim; // dim orthogonal to cutting plane ANNcoord cut_val; // location of cutting plane ANNcoord cd_bnds[2]; // lower and upper bounds of // rectangle along cut_dim ANNkd_ptr child[2]; // left and right children public: ANNkd_split( // constructor int cd, // cutting dimension ANNcoord cv, // cutting value ANNcoord lv, ANNcoord hv, // low and high values ANNkd_ptr lc=NULL, ANNkd_ptr hc=NULL) // children { cut_dim = cd; // cutting dimension cut_val = cv; // cutting value cd_bnds[ANN_LO] = lv; // lower bound for rectangle cd_bnds[ANN_HI] = hv; // upper bound for rectangle child[ANN_LO] = lc; // left child child[ANN_HI] = hc; // right child parent = NULL; } ~ANNkd_split() // destructor { if (child[ANN_LO]!= NULL && child[ANN_LO]!= KD_TRIVIAL) delete child[ANN_LO]; if (child[ANN_HI]!= NULL && child[ANN_HI]!= KD_TRIVIAL) delete child[ANN_HI]; } virtual void getStats( // get tree statistics int dim, // dimension of space ANNkdStats &st, // statistics ANNorthRect &bnd_box); // bounding box virtual void print(int level, ostream &out);// print node #ifndef FOR_R_TDA virtual void dump(ostream &out); // dump node #endif virtual void ann_search(ANNdist); // standard search virtual void ann_pri_search(ANNdist); // priority search virtual void ann_FR_search(ANNdist); // fixed-radius search /////// void delete_leaf(ANNkd_leaf* childToDelete); // set the leaf to KD_TRIVIAL // range search virtual void range_search(const ANNorthRect& region, // query region int ANNkdDim, // dimension of points, ANNpointArray ANNkdPts, // array of points ANNorthRect& bnd_box, // bounding box of the current node, // comes precomputed from the caller std::vector& pointIdices); // indices of points are returned in this vector virtual void range_search_add(std::vector& pointIdices); // add all points to pointIdices }; //---------------------------------------------------------------------- // External entry points //---------------------------------------------------------------------- ANNkd_ptr rkd_tree( // recursive construction of kd-tree ANNpointArray pa, // point array (unaltered) ANNidxArray pidx, // point indices to store in subtree int n, // number of points int dim, // dimension of space int bsp, // bucket space ANNorthRect &bnd_box, // bounding box for current node ANNkd_splitter splitter, // splitting routine vector* ppointToLeafVec); } #endif