# ITE / code / shared / embedded / ann_wrapperM / @ann / private / bd_tree.h

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100``` ```//---------------------------------------------------------------------- // File: bd_tree.h // Programmer: David Mount // Description: Declarations for standard bd-tree routines // Last modified: 01/04/05 (Version 1.0) //---------------------------------------------------------------------- // 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.0 04/01/05 // Changed IN, OUT to ANN_IN, ANN_OUT //---------------------------------------------------------------------- #ifndef ANN_bd_tree_H #define ANN_bd_tree_H #include "ANNx.h" // all ANN includes #include "kd_tree.h" // kd-tree includes //---------------------------------------------------------------------- // bd-tree shrinking node. // The main addition in the bd-tree is the shrinking node, which // is declared here. // // Shrinking nodes are defined by list of orthogonal halfspaces. // These halfspaces define a (possibly unbounded) orthogonal // rectangle. There are two children, in and out. Points that // lie within this rectangle are stored in the in-child, and the // other points are stored in the out-child. // // We use a list of orthogonal halfspaces rather than an // orthogonal rectangle object because typically the number of // sides of the shrinking box will be much smaller than the // worst case bound of 2*dim. // // BEWARE: Note that constructor just copies the pointer to the // bounding array, but the destructor deallocates it. This is // rather poor practice, but happens to be convenient. The list // is allocated in the bd-tree building procedure rbd_tree() just // prior to construction, and is used for no other purposes. // // WARNING: In the near neighbor searching code it is assumed that // the list of bounding halfspaces is irredundant, meaning that there // are no two distinct halfspaces in the list with the same outward // pointing normals. //---------------------------------------------------------------------- class ANNbd_shrink : public ANNkd_node // splitting node of a kd-tree { int n_bnds; // number of bounding halfspaces ANNorthHSArray bnds; // list of bounding halfspaces ANNkd_ptr child[2]; // in and out children public: ANNbd_shrink( // constructor int nb, // number of bounding halfspaces ANNorthHSArray bds, // list of bounding halfspaces ANNkd_ptr ic=NULL, ANNkd_ptr oc=NULL) // children { n_bnds = nb; // cutting dimension bnds = bds; // assign bounds child[ANN_IN] = ic; // set children child[ANN_OUT] = oc; } ~ANNbd_shrink() // destructor { if (child[ANN_IN]!= NULL && child[ANN_IN]!= KD_TRIVIAL) delete child[ANN_IN]; if (child[ANN_OUT]!= NULL&& child[ANN_OUT]!= KD_TRIVIAL) delete child[ANN_OUT]; if (bnds != NULL) delete [] bnds; // delete bounds } 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 }; #endif ```