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
|
//----------------------------------------------------------------------
// File: ann_sample.cpp
// Programmer: Sunil Arya and David Mount
// Last modified: 03/04/98 (Release 0.1)
// Description: Sample program for ANN
//----------------------------------------------------------------------
// 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.
//----------------------------------------------------------------------
#include <cstdlib> // C standard library
#include <cstdio> // C I/O (for sscanf)
#include <cstring> // string manipulation
#include <fstream> // file I/O
#include <ANN/ANN.h> // ANN declarations
using namespace std; // make std:: accessible
//----------------------------------------------------------------------
// ann_sample
//
// This is a simple sample program for the ANN library. After compiling,
// it can be run as follows.
//
// ann_sample [-d dim] [-max mpts] [-nn k] [-e eps] [-df data] [-qf query]
//
// where
// dim is the dimension of the space (default = 2)
// mpts maximum number of data points (default = 1000)
// k number of nearest neighbors per query (default 1)
// eps is the error bound (default = 0.0)
// data file containing data points
// query file containing query points
//
// Results are sent to the standard output.
//----------------------------------------------------------------------
//----------------------------------------------------------------------
// Parameters that are set in getArgs()
//----------------------------------------------------------------------
void getArgs(int argc, char **argv); // get command-line arguments
int k = 1; // number of nearest neighbors
int dim = 2; // dimension
double eps = 0; // error bound
int maxPts = 1000; // maximum number of data points
istream* dataIn = NULL; // input for data points
istream* queryIn = NULL; // input for query points
bool readPt(istream &in, ANNpoint p) // read point (false on EOF)
{
for (int i = 0; i < dim; i++) {
if(!(in >> p[i])) return false;
}
return true;
}
void printPt(ostream &out, ANNpoint p) // print point
{
out << "(" << p[0];
for (int i = 1; i < dim; i++) {
out << ", " << p[i];
}
out << ")\n";
}
int main(int argc, char **argv)
{
int nPts; // actual number of data points
ANNpointArray dataPts; // data points
ANNpoint queryPt; // query point
ANNidxArray nnIdx; // near neighbor indices
ANNdistArray dists; // near neighbor distances
ANNkd_tree* kdTree; // search structure
getArgs(argc, argv); // read command-line arguments
queryPt = annAllocPt(dim); // allocate query point
dataPts = annAllocPts(maxPts, dim); // allocate data points
nnIdx = new ANNidx[k]; // allocate near neigh indices
dists = new ANNdist[k]; // allocate near neighbor dists
nPts = 0; // read data points
cout << "Data Points:\n";
while (nPts < maxPts && readPt(*dataIn, dataPts[nPts])) {
printPt(cout, dataPts[nPts]);
nPts++;
}
kdTree = new ANNkd_tree( // build search structure
dataPts, // the data points
nPts, // number of points
dim); // dimension of space
while (readPt(*queryIn, queryPt)) { // read query points
cout << "Query point: "; // echo query point
printPt(cout, queryPt);
kdTree->annkSearch( // search
queryPt, // query point
k, // number of near neighbors
nnIdx, // nearest neighbors (returned)
dists, // distance (returned)
eps); // error bound
cout << "\tNN:\tIndex\tDistance\n";
for (int i = 0; i < k; i++) { // print summary
dists[i] = sqrt(dists[i]); // unsquare distance
cout << "\t" << i << "\t" << nnIdx[i] << "\t" << dists[i] << "\n";
}
}
delete [] nnIdx; // clean things up
delete [] dists;
delete kdTree;
annClose(); // done with ANN
return EXIT_SUCCESS;
}
//----------------------------------------------------------------------
// getArgs - get command line arguments
//----------------------------------------------------------------------
void getArgs(int argc, char **argv)
{
static ifstream dataStream; // data file stream
static ifstream queryStream; // query file stream
if (argc <= 1) { // no arguments
cerr << "Usage:\n\n"
<< " ann_sample [-d dim] [-max m] [-nn k] [-e eps] [-df data]"
" [-qf query]\n\n"
<< " where:\n"
<< " dim dimension of the space (default = 2)\n"
<< " m maximum number of data points (default = 1000)\n"
<< " k number of nearest neighbors per query (default 1)\n"
<< " eps the error bound (default = 0.0)\n"
<< " data name of file containing data points\n"
<< " query name of file containing query points\n\n"
<< " Results are sent to the standard output.\n"
<< "\n"
<< " To run this demo use:\n"
<< " ann_sample -df data.pts -qf query.pts\n";
exit(0);
}
int i = 1;
while (i < argc) { // read arguments
if (!strcmp(argv[i], "-d")) { // -d option
dim = atoi(argv[++i]); // get dimension to dump
}
else if (!strcmp(argv[i], "-max")) { // -max option
maxPts = atoi(argv[++i]); // get max number of points
}
else if (!strcmp(argv[i], "-nn")) { // -nn option
k = atoi(argv[++i]); // get number of near neighbors
}
else if (!strcmp(argv[i], "-e")) { // -e option
sscanf(argv[++i], "%lf", &eps); // get error bound
}
else if (!strcmp(argv[i], "-df")) { // -df option
dataStream.open(argv[++i], ios::in);// open data file
if (!dataStream) {
cerr << "Cannot open data file\n";
exit(1);
}
dataIn = &dataStream; // make this the data stream
}
else if (!strcmp(argv[i], "-qf")) { // -qf option
queryStream.open(argv[++i], ios::in);// open query file
if (!queryStream) {
cerr << "Cannot open query file\n";
exit(1);
}
queryIn = &queryStream; // make this query stream
}
else { // illegal syntax
cerr << "Unrecognized option.\n";
exit(1);
}
i++;
}
if (dataIn == NULL || queryIn == NULL) {
cerr << "-df and -qf options must be specified\n";
exit(1);
}
}
|
