kd_tree.h
上传用户:chinafayin
上传日期:2022-04-05
资源大小:153k
文件大小:8k
- //----------------------------------------------------------------------
- // 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
- //----------------------------------------------------------------------
- #ifndef ANN_kd_tree_H
- #define ANN_kd_tree_H
- #include "../ANNx.h" // all ANN includes
- using namespace std; // make std:: available
- //----------------------------------------------------------------------
- // 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{ // generic kd-tree node (empty shell)
- public:
- 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;
- virtual void dump(ostream &out) = 0; // dump node
- friend class ANNkd_tree; // allow kd-tree to access us
- };
- //----------------------------------------------------------------------
- // 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; // no. points in bucket
- ANNidxArray bkt; // bucket of points
- public:
- ANNkd_leaf( // constructor
- int n, // number of points
- ANNidxArray b) // bucket
- {
- n_pts = n; // number of points in bucket
- bkt = b; // the bucket
- }
- ~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
- virtual void dump(ostream &out); // dump node
- virtual void ann_search(ANNdist); // standard search
- virtual void ann_pri_search(ANNdist); // priority search
- virtual void ann_FR_search(ANNdist); // fixed-radius search
- };
- //----------------------------------------------------------------------
- // 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
- }
- ~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
- virtual void dump(ostream &out); // dump node
- virtual void ann_search(ANNdist); // standard search
- virtual void ann_pri_search(ANNdist); // priority search
- virtual void ann_FR_search(ANNdist); // fixed-radius search
- };
- //----------------------------------------------------------------------
- // 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
- #endif