00001 //---------------------------------------------------------------------- 00002 // File: ANN.cpp 00003 // Programmer: Sunil Arya and David Mount 00004 // Description: Methods for ANN.h and ANNx.h 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 // Added performance counting to annDist() 00025 //---------------------------------------------------------------------- 00026 00027 #include <stdlib.h> 00028 #include <stereo_wall_detection/ANN/ANNx.h> // all ANN includes 00029 #include <stereo_wall_detection/ANN/ANNperf.h> // ANN performance 00030 00031 using namespace std; // make std:: accessible 00032 00033 //---------------------------------------------------------------------- 00034 // Point methods 00035 //---------------------------------------------------------------------- 00036 00037 //---------------------------------------------------------------------- 00038 // Distance utility. 00039 // (Note: In the nearest neighbor search, most distances are 00040 // computed using partial distance calculations, not this 00041 // procedure.) 00042 //---------------------------------------------------------------------- 00043 00044 ANNdist annDist( // interpoint squared distance 00045 int dim, 00046 ANNpoint p, 00047 ANNpoint q) 00048 { 00049 register int d; 00050 register ANNcoord diff; 00051 register ANNcoord dist; 00052 00053 dist = 0; 00054 for (d = 0; d < dim; d++) { 00055 diff = p[d] - q[d]; 00056 dist = ANN_SUM(dist, ANN_POW(diff)); 00057 } 00058 ANN_FLOP(3*dim) // performance counts 00059 ANN_PTS(1) 00060 ANN_COORD(dim) 00061 return dist; 00062 } 00063 00064 //---------------------------------------------------------------------- 00065 // annPrintPoint() prints a point to a given output stream. 00066 //---------------------------------------------------------------------- 00067 00068 void annPrintPt( // print a point 00069 ANNpoint pt, // the point 00070 int dim, // the dimension 00071 std::ostream &out) // output stream 00072 { 00073 for (int j = 0; j < dim; j++) { 00074 out << pt[j]; 00075 if (j < dim-1) out << " "; 00076 } 00077 } 00078 00079 //---------------------------------------------------------------------- 00080 // Point allocation/deallocation: 00081 // 00082 // Because points (somewhat like strings in C) are stored 00083 // as pointers. Consequently, creating and destroying 00084 // copies of points may require storage allocation. These 00085 // procedures do this. 00086 // 00087 // annAllocPt() and annDeallocPt() allocate a deallocate 00088 // storage for a single point, and return a pointer to it. 00089 // 00090 // annAllocPts() allocates an array of points as well a place 00091 // to store their coordinates, and initializes the points to 00092 // point to their respective coordinates. It allocates point 00093 // storage in a contiguous block large enough to store all the 00094 // points. It performs no initialization. 00095 // 00096 // annDeallocPts() should only be used on point arrays allocated 00097 // by annAllocPts since it assumes that points are allocated in 00098 // a block. 00099 // 00100 // annCopyPt() copies a point taking care to allocate storage 00101 // for the new point. 00102 // 00103 // annAssignRect() assigns the coordinates of one rectangle to 00104 // another. The two rectangles must have the same dimension 00105 // (and it is not possible to test this here). 00106 //---------------------------------------------------------------------- 00107 00108 ANNpoint annAllocPt(int dim, ANNcoord c) // allocate 1 point 00109 { 00110 ANNpoint p = new ANNcoord[dim]; 00111 for (int i = 0; i < dim; i++) p[i] = c; 00112 return p; 00113 } 00114 00115 ANNpointArray annAllocPts(int n, int dim) // allocate n pts in dim 00116 { 00117 ANNpointArray pa = new ANNpoint[n]; // allocate points 00118 ANNpoint p = new ANNcoord[n*dim]; // allocate space for coords 00119 for (int i = 0; i < n; i++) { 00120 pa[i] = &(p[i*dim]); 00121 } 00122 return pa; 00123 } 00124 00125 void annDeallocPt(ANNpoint &p) // deallocate 1 point 00126 { 00127 delete [] p; 00128 p = NULL; 00129 } 00130 00131 void annDeallocPts(ANNpointArray &pa) // deallocate points 00132 { 00133 delete [] pa[0]; // dealloc coordinate storage 00134 delete [] pa; // dealloc points 00135 pa = NULL; 00136 } 00137 00138 ANNpoint annCopyPt(int dim, ANNpoint source) // copy point 00139 { 00140 ANNpoint p = new ANNcoord[dim]; 00141 for (int i = 0; i < dim; i++) p[i] = source[i]; 00142 return p; 00143 } 00144 00145 // assign one rect to another 00146 void annAssignRect(int dim, ANNorthRect &dest, const ANNorthRect &source) 00147 { 00148 for (int i = 0; i < dim; i++) { 00149 dest.lo[i] = source.lo[i]; 00150 dest.hi[i] = source.hi[i]; 00151 } 00152 } 00153 00154 // is point inside rectangle? 00155 ANNbool ANNorthRect::inside(int dim, ANNpoint p) 00156 { 00157 for (int i = 0; i < dim; i++) { 00158 if (p[i] < lo[i] || p[i] > hi[i]) return ANNfalse; 00159 } 00160 return ANNtrue; 00161 } 00162 00163 //---------------------------------------------------------------------- 00164 // Error handler 00165 //---------------------------------------------------------------------- 00166 00167 void annError(const char *msg, ANNerr level) 00168 { 00169 if (level == ANNabort) { 00170 cerr << "ANN: ERROR------->" << msg << "<-------------ERROR\n"; 00171 exit(1); 00172 } 00173 else { 00174 cerr << "ANN: WARNING----->" << msg << "<-------------WARNING\n"; 00175 } 00176 } 00177 00178 //---------------------------------------------------------------------- 00179 // Limit on number of points visited 00180 // We have an option for terminating the search early if the 00181 // number of points visited exceeds some threshold. If the 00182 // threshold is 0 (its default) this means there is no limit 00183 // and the algorithm applies its normal termination condition. 00184 // This is for applications where there are real time constraints 00185 // on the running time of the algorithm. 00186 //---------------------------------------------------------------------- 00187 00188 int ANNmaxPtsVisited = 0; // maximum number of pts visited 00189 int ANNptsVisited; // number of pts visited in search 00190 00191 //---------------------------------------------------------------------- 00192 // Global function declarations 00193 //---------------------------------------------------------------------- 00194 00195 void annMaxPtsVisit( // set limit on max. pts to visit in search 00196 int maxPts) // the limit 00197 { 00198 ANNmaxPtsVisited = maxPts; 00199 }