bd_tree.h
Go to the documentation of this file.00001 //---------------------------------------------------------------------- 00002 // File: bd_tree.h 00003 // Programmer: David Mount 00004 // Description: Declarations for standard bd-tree routines 00005 // Last modified: 01/04/05 (Version 1.0) 00006 //---------------------------------------------------------------------- 00007 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and 00008 // David Mount. All Rights Reserved. 00009 // 00010 // This software and related documentation is part of the Approximate 00011 // Nearest Neighbor Library (ANN). This software is provided under 00012 // the provisions of the Lesser GNU Public License (LGPL). See the 00013 // file ../ReadMe.txt for further information. 00014 // 00015 // The University of Maryland (U.M.) and the authors make no 00016 // representations about the suitability or fitness of this software for 00017 // any purpose. It is provided "as is" without express or implied 00018 // warranty. 00019 //---------------------------------------------------------------------- 00020 // History: 00021 // Revision 0.1 03/04/98 00022 // Initial release 00023 // Revision 1.0 04/01/05 00024 // Changed IN, OUT to ANN_IN, ANN_OUT 00025 //---------------------------------------------------------------------- 00026 00027 #ifndef ANN_bd_tree_H 00028 #define ANN_bd_tree_H 00029 00030 #include <stereo_wall_detection/ANN/ANNx.h> // all ANN includes 00031 #include "kd_tree.h" // kd-tree includes 00032 00033 //---------------------------------------------------------------------- 00034 // bd-tree shrinking node. 00035 // The main addition in the bd-tree is the shrinking node, which 00036 // is declared here. 00037 // 00038 // Shrinking nodes are defined by list of orthogonal halfspaces. 00039 // These halfspaces define a (possibly unbounded) orthogonal 00040 // rectangle. There are two children, in and out. Points that 00041 // lie within this rectangle are stored in the in-child, and the 00042 // other points are stored in the out-child. 00043 // 00044 // We use a list of orthogonal halfspaces rather than an 00045 // orthogonal rectangle object because typically the number of 00046 // sides of the shrinking box will be much smaller than the 00047 // worst case bound of 2*dim. 00048 // 00049 // BEWARE: Note that constructor just copies the pointer to the 00050 // bounding array, but the destructor deallocates it. This is 00051 // rather poor practice, but happens to be convenient. The list 00052 // is allocated in the bd-tree building procedure rbd_tree() just 00053 // prior to construction, and is used for no other purposes. 00054 // 00055 // WARNING: In the near neighbor searching code it is assumed that 00056 // the list of bounding halfspaces is irredundant, meaning that there 00057 // are no two distinct halfspaces in the list with the same outward 00058 // pointing normals. 00059 //---------------------------------------------------------------------- 00060 00061 class ANNbd_shrink : public ANNkd_node // splitting node of a kd-tree 00062 { 00063 int n_bnds; // number of bounding halfspaces 00064 ANNorthHSArray bnds; // list of bounding halfspaces 00065 ANNkd_ptr child[2]; // in and out children 00066 public: 00067 ANNbd_shrink( // constructor 00068 int nb, // number of bounding halfspaces 00069 ANNorthHSArray bds, // list of bounding halfspaces 00070 ANNkd_ptr ic=NULL, ANNkd_ptr oc=NULL) // children 00071 { 00072 n_bnds = nb; // cutting dimension 00073 bnds = bds; // assign bounds 00074 child[ANN_IN] = ic; // set children 00075 child[ANN_OUT] = oc; 00076 } 00077 00078 ~ANNbd_shrink() // destructor 00079 { 00080 if (child[ANN_IN]!= NULL && child[ANN_IN]!= KD_TRIVIAL) 00081 delete child[ANN_IN]; 00082 if (child[ANN_OUT]!= NULL&& child[ANN_OUT]!= KD_TRIVIAL) 00083 delete child[ANN_OUT]; 00084 if (bnds != NULL) 00085 delete [] bnds; // delete bounds 00086 } 00087 00088 virtual void getStats( // get tree statistics 00089 int dim, // dimension of space 00090 ANNkdStats &st, // statistics 00091 ANNorthRect &bnd_box); // bounding box 00092 virtual void print(int level, ostream &out);// print node 00093 virtual void dump(ostream &out); // dump node 00094 00095 virtual void ann_search(ANNdist); // standard search 00096 virtual void ann_pri_search(ANNdist); // priority search 00097 virtual void ann_FR_search(ANNdist); // fixed-radius search 00098 }; 00099 00100 #endif