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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
|
//----------------------------------------------------------------------
// File: ANN.cpp
// Programmer: Sunil Arya and David Mount
// Description: Methods for ANN.h and ANNx.h
// Last modified: 01/27/10 (Version 1.1.2)
//----------------------------------------------------------------------
// Copyright (c) 1997-2010 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
// Added performance counting to annDist()
// Revision 1.1.2 01/27/10
// Fixed minor compilation bugs for new versions of gcc
//----------------------------------------------------------------------
#ifdef _WIN32
#include <ciso646> // make VS more conformal
#endif
#include <stdexcept>
#include <cstdlib> // C standard lib defs
#include <ANN/ANNx.h> // all ANN includes
#include <ANN/ANNperf.h> // ANN performance
#include "def_debug_bt.h"
using namespace std; // make std:: accessible
namespace geom_bt {
//----------------------------------------------------------------------
// Point methods
//----------------------------------------------------------------------
//----------------------------------------------------------------------
// Distance utility.
// (Note: In the nearest neighbor search, most distances are
// computed using partial distance calculations, not this
// procedure.)
//----------------------------------------------------------------------
ANNdist annDist( // interpoint squared distance
int dim,
ANNpoint p,
ANNpoint q)
{
register int d;
register ANNcoord diff;
register ANNcoord dist;
dist = 0;
for (d = 0; d < dim; d++) {
diff = p[d] - q[d];
dist = ANN_SUM(dist, ANN_POW(diff));
}
ANN_FLOP(3*dim) // performance counts
ANN_PTS(1)
ANN_COORD(dim)
return dist;
}
//----------------------------------------------------------------------
// annPrintPoint() prints a point to a given output stream.
//----------------------------------------------------------------------
void annPrintPt( // print a point
ANNpoint pt, // the point
int dim, // the dimension
std::ostream &out) // output stream
{
#ifndef FOR_R_TDA
for (int j = 0; j < dim; j++) {
out << pt[j];
if (j < dim-1) out << " ";
}
#endif
}
//----------------------------------------------------------------------
// Point allocation/deallocation:
//
// Because points (somewhat like strings in C) are stored
// as pointers. Consequently, creating and destroying
// copies of points may require storage allocation. These
// procedures do this.
//
// annAllocPt() and annDeallocPt() allocate a deallocate
// storage for a single point, and return a pointer to it.
//
// annAllocPts() allocates an array of points as well a place
// to store their coordinates, and initializes the points to
// point to their respective coordinates. It allocates point
// storage in a contiguous block large enough to store all the
// points. It performs no initialization.
//
// annDeallocPts() should only be used on point arrays allocated
// by annAllocPts since it assumes that points are allocated in
// a block.
//
// annCopyPt() copies a point taking care to allocate storage
// for the new point.
//
// annAssignRect() assigns the coordinates of one rectangle to
// another. The two rectangles must have the same dimension
// (and it is not possible to test this here).
//----------------------------------------------------------------------
ANNpoint annAllocPt(int dim, ANNcoord c) // allocate 1 point
{
ANNpoint p = new ANNcoord[dim];
for (int i = 0; i < dim; i++) p[i] = c;
return p;
}
ANNpointArray annAllocPts(int n, int dim) // allocate n pts in dim
{
ANNpointArray pa = new ANNpoint[n]; // allocate points
ANNpoint p = new ANNcoord[n*dim]; // allocate space for coords
for (int i = 0; i < n; i++) {
pa[i] = &(p[i*dim]);
}
return pa;
}
void annDeallocPt(ANNpoint &p) // deallocate 1 point
{
delete [] p;
p = NULL;
}
void annDeallocPts(ANNpointArray &pa) // deallocate points
{
delete [] pa[0]; // dealloc coordinate storage
delete [] pa; // dealloc points
pa = NULL;
}
ANNpoint annCopyPt(int dim, ANNpoint source) // copy point
{
ANNpoint p = new ANNcoord[dim];
for (int i = 0; i < dim; i++) p[i] = source[i];
return p;
}
// assign one rect to another
void annAssignRect(int dim, ANNorthRect &dest, const ANNorthRect &source)
{
for (int i = 0; i < dim; i++) {
dest.lo[i] = source.lo[i];
dest.hi[i] = source.hi[i];
}
}
// is point inside rectangle?
ANNbool ANNorthRect::inside(const int dim, ANNpoint p) const
{
for (int i = 0; i < dim; i++) {
if (p[i] < lo[i] || p[i] > hi[i]) return ANNfalse;
}
return ANNtrue;
}
bool ANNorthRect::contains(const int dim, const ANNorthRect& r) const
{
return this->inside(dim, r.hi) and this->inside(dim, r.lo);
}
bool ANNorthRect::intersects(const int dim, const ANNorthRect& r) const
{
assert(dim == 2); // works for plane only
const ANNpoint otherLo = r.lo;
const ANNpoint otherHi = r.hi;
if ( otherLo[0] > hi[0] or
otherLo[1] > hi[1] or
otherHi[0] < lo[0] or
otherHi[1] < lo[1]) {
return false;
} else {
return true;
}
}
//----------------------------------------------------------------------
// Error handler
//----------------------------------------------------------------------
void annError(const char* msg, ANNerr level)
{
if (level == ANNabort) {
#ifndef FOR_R_TDA
cerr << "ANN: ERROR------->" << msg << "<-------------ERROR\n";
#endif
throw std::runtime_error(std::string("ANN: Error: ") + std::string(msg));
//exit(1);
}
else {
#ifndef FOR_R_TDA
cerr << "ANN: WARNING----->" << msg << "<-------------WARNING\n";
#endif
}
}
//----------------------------------------------------------------------
// Limit on number of points visited
// We have an option for terminating the search early if the
// number of points visited exceeds some threshold. If the
// threshold is 0 (its default) this means there is no limit
// and the algorithm applies its normal termination condition.
// This is for applications where there are real time constraints
// on the running time of the algorithm.
//----------------------------------------------------------------------
int ANNmaxPtsVisited = 0; // maximum number of pts visited
int ANNptsVisited; // number of pts visited in search
//----------------------------------------------------------------------
// Global function declarations
//----------------------------------------------------------------------
void annMaxPtsVisit( // set limit on max. pts to visit in search
int maxPts) // the limit
{
ANNmaxPtsVisited = maxPts;
}
}
|
