queso-0.57.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
ANN.cpp
Go to the documentation of this file.
1 //----------------------------------------------------------------------
2 // File: ANN.cpp
3 // Programmer: Sunil Arya and David Mount
4 // Description: Methods for ANN.h and ANNx.h
5 // Last modified: 01/27/10 (Version 1.1.2)
6 //----------------------------------------------------------------------
7 // Copyright (c) 1997-2010 University of Maryland and Sunil Arya and
8 // David Mount. All Rights Reserved.
9 //
10 // This software and related documentation is part of the Approximate
11 // Nearest Neighbor Library (ANN). This software is provided under
12 // the provisions of the Lesser GNU Public License (LGPL). See the
13 // file ../ReadMe.txt for further information.
14 //
15 // The University of Maryland (U.M.) and the authors make no
16 // representations about the suitability or fitness of this software for
17 // any purpose. It is provided "as is" without express or implied
18 // warranty.
19 //----------------------------------------------------------------------
20 // History:
21 // Revision 0.1 03/04/98
22 // Initial release
23 // Revision 1.0 04/01/05
24 // Added performance counting to annDist()
25 // Revision 1.1.2 01/27/10
26 // Fixed minor compilation bugs for new versions of gcc
27 //----------------------------------------------------------------------
28 
29 #include <cstdlib> // C standard lib defs
30 #include <ANN/ANNx.h> // all ANN includes
31 #include <ANN/ANNperf.h> // ANN performance
32 
33 using namespace std; // make std:: accessible
34 
35 //----------------------------------------------------------------------
36 // Point methods
37 //----------------------------------------------------------------------
38 
39 //----------------------------------------------------------------------
40 // Distance utility.
41 // (Note: In the nearest neighbor search, most distances are
42 // computed using partial distance calculations, not this
43 // procedure.)
44 //----------------------------------------------------------------------
45 
46 ANNdist annDist( // interpoint squared distance
47  int dim,
48  ANNpoint p,
49  ANNpoint q)
50 {
51  register int d;
52  register ANNcoord diff;
53  register ANNcoord dist;
54 
55  dist = 0;
56  for (d = 0; d < dim; d++) {
57  diff = p[d] - q[d];
58  dist = ANN_SUM(dist, ANN_POW(diff));
59  }
60  ANN_FLOP(3*dim) // performance counts
61  ANN_PTS(1)
62  ANN_COORD(dim)
63  return dist;
64 }
65 
66 //----------------------------------------------------------------------
67 // annPrintPoint() prints a point to a given output stream.
68 //----------------------------------------------------------------------
69 
70 void annPrintPt( // print a point
71  ANNpoint pt, // the point
72  int dim, // the dimension
73  std::ostream &out) // output stream
74 {
75  for (int j = 0; j < dim; j++) {
76  out << pt[j];
77  if (j < dim-1) out << " ";
78  }
79 }
80 
81 //----------------------------------------------------------------------
82 // Point allocation/deallocation:
83 //
84 // Because points (somewhat like strings in C) are stored
85 // as pointers. Consequently, creating and destroying
86 // copies of points may require storage allocation. These
87 // procedures do this.
88 //
89 // annAllocPt() and annDeallocPt() allocate a deallocate
90 // storage for a single point, and return a pointer to it.
91 //
92 // annAllocPts() allocates an array of points as well a place
93 // to store their coordinates, and initializes the points to
94 // point to their respective coordinates. It allocates point
95 // storage in a contiguous block large enough to store all the
96 // points. It performs no initialization.
97 //
98 // annDeallocPts() should only be used on point arrays allocated
99 // by annAllocPts since it assumes that points are allocated in
100 // a block.
101 //
102 // annCopyPt() copies a point taking care to allocate storage
103 // for the new point.
104 //
105 // annAssignRect() assigns the coordinates of one rectangle to
106 // another. The two rectangles must have the same dimension
107 // (and it is not possible to test this here).
108 //----------------------------------------------------------------------
109 
110 ANNpoint annAllocPt(int dim, ANNcoord c) // allocate 1 point
111 {
112  ANNpoint p = new ANNcoord[dim];
113  for (int i = 0; i < dim; i++) p[i] = c;
114  return p;
115 }
116 
117 ANNpointArray annAllocPts(int n, int dim) // allocate n pts in dim
118 {
119  ANNpointArray pa = new ANNpoint[n]; // allocate points
120  ANNpoint p = new ANNcoord[n*dim]; // allocate space for coords
121  for (int i = 0; i < n; i++) {
122  pa[i] = &(p[i*dim]);
123  }
124  return pa;
125 }
126 
127 void annDeallocPt(ANNpoint &p) // deallocate 1 point
128 {
129  delete [] p;
130  p = NULL;
131 }
132 
133 void annDeallocPts(ANNpointArray &pa) // deallocate points
134 {
135  delete [] pa[0]; // dealloc coordinate storage
136  delete [] pa; // dealloc points
137  pa = NULL;
138 }
139 
140 ANNpoint annCopyPt(int dim, ANNpoint source) // copy point
141 {
142  ANNpoint p = new ANNcoord[dim];
143  for (int i = 0; i < dim; i++) p[i] = source[i];
144  return p;
145 }
146 
147  // assign one rect to another
148 void annAssignRect(int dim, ANNorthRect &dest, const ANNorthRect &source)
149 {
150  for (int i = 0; i < dim; i++) {
151  dest.lo[i] = source.lo[i];
152  dest.hi[i] = source.hi[i];
153  }
154 }
155 
156  // is point inside rectangle?
158 {
159  for (int i = 0; i < dim; i++) {
160  if (p[i] < lo[i] || p[i] > hi[i]) return ANNfalse;
161  }
162  return ANNtrue;
163 }
164 
165 //----------------------------------------------------------------------
166 // Error handler
167 //----------------------------------------------------------------------
168 
169 void annError(const char* msg, ANNerr level)
170 {
171  if (level == ANNabort) {
172  cerr << "ANN: ERROR------->" << msg << "<-------------ERROR\n";
173  exit(1);
174  }
175  else {
176  cerr << "ANN: WARNING----->" << msg << "<-------------WARNING\n";
177  }
178 }
179 
180 //----------------------------------------------------------------------
181 // Limit on number of points visited
182 // We have an option for terminating the search early if the
183 // number of points visited exceeds some threshold. If the
184 // threshold is 0 (its default) this means there is no limit
185 // and the algorithm applies its normal termination condition.
186 // This is for applications where there are real time constraints
187 // on the running time of the algorithm.
188 //----------------------------------------------------------------------
189 
190 int ANNmaxPtsVisited = 0; // maximum number of pts visited
191 int ANNptsVisited; // number of pts visited in search
192 
193 //----------------------------------------------------------------------
194 // Global function declarations
195 //----------------------------------------------------------------------
196 
197 void annMaxPtsVisit( // set limit on max. pts to visit in search
198  int maxPts) // the limit
199 {
200  ANNmaxPtsVisited = maxPts;
201 }
ANNpoint * ANNpointArray
Definition: ANN.h:376
void annPrintPt(ANNpoint pt, int dim, std::ostream &out)
Definition: ANN.cpp:70
ANNpoint hi
Definition: ANNx.h:94
DLL_API void annDeallocPt(ANNpoint &p)
Definition: ANN.cpp:127
double ANNcoord
Definition: ANN.h:158
double ANNdist
Definition: ANN.h:159
ANNerr
Definition: ANNx.h:48
ANNcoord * ANNpoint
Definition: ANN.h:375
int ANNptsVisited
Definition: ANN.cpp:191
ANNpoint lo
Definition: ANNx.h:93
DLL_API void annDeallocPts(ANNpointArray &pa)
Definition: ANN.cpp:133
Definition: ANNx.h:48
DLL_API ANNpoint annAllocPt(int dim, ANNcoord c=0)
Definition: ANN.cpp:110
DLL_API ANNdist annDist(int dim, ANNpoint p, ANNpoint q)
Definition: ANN.cpp:46
int ANNmaxPtsVisited
Definition: ANN.cpp:190
int dim
Definition: ann_test.cpp:472
Definition: ANN.h:132
DLL_API ANNpoint annCopyPt(int dim, ANNpoint source)
Definition: ANN.cpp:140
DLL_API void annMaxPtsVisit(int maxPts)
Definition: ANN.cpp:197
DLL_API ANNpointArray annAllocPts(int n, int dim)
Definition: ANN.cpp:117
void annError(const char *msg, ANNerr level)
Definition: ANN.cpp:169
Definition: ANN.h:132
ANNbool
Definition: ANN.h:132
ANNbool inside(int dim, ANNpoint p)
Definition: ANN.cpp:157
void annAssignRect(int dim, ANNorthRect &dest, const ANNorthRect &source)
Definition: ANN.cpp:148

Generated on Tue Jun 5 2018 19:48:54 for queso-0.57.1 by  doxygen 1.8.5