diff options
Diffstat (limited to 'geom_bottleneck/bottleneck/include/ANN/kd_tree.h')
| -rw-r--r-- | geom_bottleneck/bottleneck/include/ANN/kd_tree.h | 260 |
1 files changed, 0 insertions, 260 deletions
diff --git a/geom_bottleneck/bottleneck/include/ANN/kd_tree.h b/geom_bottleneck/bottleneck/include/ANN/kd_tree.h deleted file mode 100644 index a1e53e5..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/kd_tree.h +++ /dev/null @@ -1,260 +0,0 @@ -//---------------------------------------------------------------------- -// 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 <utility> // for std::pair -#include <ANN/ANNx.h> // 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<ANNidx, ANNkd_node*> 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<size_t>& pointIdices) {} // indices of points are returned in this vector - virtual void range_search_add(std::vector<size_t>& 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<size_t>& pointIdices); // indices of points are returned in this vector - virtual void range_search_add(std::vector<size_t>& 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<size_t>& pointIdices); // indices of points are returned in this vector - virtual void range_search_add(std::vector<size_t>& 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<ANNkd_leaf*>* ppointToLeafVec); - -} -#endif |