Debian Codegraph @

sample/ann_sample.cpp

raw
1 //----------------------------------------------------------------------
2 // File: ann_sample.cpp
3 // Programmer: Sunil Arya and David Mount
4 // Last modified: 03/04/98 (Release 0.1)
5 // Description: Sample program for ANN
6 //----------------------------------------------------------------------
7 // Copyright (c) 1997-2005 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
21 #include <cstdlib> // C standard library
22 #include <cstdio> // C I/O (for sscanf)
23 #include <cstring> // string manipulation
24 #include <fstream> // file I/O
25 #include <ANN/ANN.h> // ANN declarations
26
27 using namespace std; // make std:: accessible
28
29 //----------------------------------------------------------------------
30 // ann_sample
31 //
32 // This is a simple sample program for the ANN library. After compiling,
33 // it can be run as follows.
34 //
35 // ann_sample [-d dim] [-max mpts] [-nn k] [-e eps] [-df data] [-qf query]
36 //
37 // where
38 // dim is the dimension of the space (default = 2)
39 // mpts maximum number of data points (default = 1000)
40 // k number of nearest neighbors per query (default 1)
41 // eps is the error bound (default = 0.0)
42 // data file containing data points
43 // query file containing query points
44 //
45 // Results are sent to the standard output.
46 //----------------------------------------------------------------------
47
48 //----------------------------------------------------------------------
49 // Parameters that are set in getArgs()
50 //----------------------------------------------------------------------
51 void getArgs(int argc, char **argv); // get command-line arguments
52
53 int k = 1; // number of nearest neighbors
54 int dim = 2; // dimension
55 double eps = 0; // error bound
56 int maxPts = 1000; // maximum number of data points
57
58 istream* dataIn = NULL; // input for data points
59 istream* queryIn = NULL; // input for query points
60
61 bool readPt(istream &in, ANNpoint p) // read point (false on EOF)
62 {
63 for (int i = 0; i < dim; i++) {
64 if(!(in >> p[i])) return false;
65 }
66 return true;
67 }
68
69 void printPt(ostream &out, ANNpoint p) // print point
70 {
71 out << "(" << p[0];
72 for (int i = 1; i < dim; i++) {
73 out << ", " << p[i];
74 }
75 out << ")\n";
76 }
77
78 int main(int argc, char **argv)
79 {
80 int nPts; // actual number of data points
81 ANNpointArray dataPts; // data points
82 ANNpoint queryPt; // query point
83 ANNidxArray nnIdx; // near neighbor indices
84 ANNdistArray dists; // near neighbor distances
85 ANNkd_tree* kdTree; // search structure
86
87 getArgs(argc, argv); // read command-line arguments
88
89 queryPt = annAllocPt(dim); // allocate query point
90 dataPts = annAllocPts(maxPts, dim); // allocate data points
91 nnIdx = new ANNidx[k]; // allocate near neigh indices
92 dists = new ANNdist[k]; // allocate near neighbor dists
93
94 nPts = 0; // read data points
95
96 cout << "Data Points:\n";
97 while (nPts < maxPts && readPt(*dataIn, dataPts[nPts])) {
98 printPt(cout, dataPts[nPts]);
99 nPts++;
100 }
101
102 kdTree = new ANNkd_tree( // build search structure
103 dataPts, // the data points
104 nPts, // number of points
105 dim); // dimension of space
106
107 while (readPt(*queryIn, queryPt)) { // read query points
108 cout << "Query point: "; // echo query point
109 printPt(cout, queryPt);
110
111 kdTree->annkSearch( // search
112 queryPt, // query point
113 k, // number of near neighbors
114 nnIdx, // nearest neighbors (returned)
115 dists, // distance (returned)
116 eps); // error bound
117
118 cout << "\tNN:\tIndex\tDistance\n";
119 for (int i = 0; i < k; i++) { // print summary
120 dists[i] = sqrt(dists[i]); // unsquare distance
121 cout << "\t" << i << "\t" << nnIdx[i] << "\t" << dists[i] << "\n";
122 }
123 }
124 delete [] nnIdx; // clean things up
125 delete [] dists;
126 delete kdTree;
127 annClose(); // done with ANN
128
129 return EXIT_SUCCESS;
130 }
131
132 //----------------------------------------------------------------------
133 // getArgs - get command line arguments
134 //----------------------------------------------------------------------
135
136 void getArgs(int argc, char **argv)
137 {
138 static ifstream dataStream; // data file stream
139 static ifstream queryStream; // query file stream
140
141 if (argc <= 1) { // no arguments
142 cerr << "Usage:\n\n"
143 << " ann_sample [-d dim] [-max m] [-nn k] [-e eps] [-df data]"
144 " [-qf query]\n\n"
145 << " where:\n"
146 << " dim dimension of the space (default = 2)\n"
147 << " m maximum number of data points (default = 1000)\n"
148 << " k number of nearest neighbors per query (default 1)\n"
149 << " eps the error bound (default = 0.0)\n"
150 << " data name of file containing data points\n"
151 << " query name of file containing query points\n\n"
152 << " Results are sent to the standard output.\n"
153 << "\n"
154 << " To run this demo use:\n"
155 << " ann_sample -df data.pts -qf query.pts\n";
156 exit(0);
157 }
158 int i = 1;
159 while (i < argc) { // read arguments
160 if (!strcmp(argv[i], "-d")) { // -d option
161 dim = atoi(argv[++i]); // get dimension to dump
162 }
163 else if (!strcmp(argv[i], "-max")) { // -max option
164 maxPts = atoi(argv[++i]); // get max number of points
165 }
166 else if (!strcmp(argv[i], "-nn")) { // -nn option
167 k = atoi(argv[++i]); // get number of near neighbors
168 }
169 else if (!strcmp(argv[i], "-e")) { // -e option
170 sscanf(argv[++i], "%lf", &eps); // get error bound
171 }
172 else if (!strcmp(argv[i], "-df")) { // -df option
173 dataStream.open(argv[++i], ios::in);// open data file
174 if (!dataStream) {
175 cerr << "Cannot open data file\n";
176 exit(1);
177 }
178 dataIn = &dataStream; // make this the data stream
179 }
180 else if (!strcmp(argv[i], "-qf")) { // -qf option
181 queryStream.open(argv[++i], ios::in);// open query file
182 if (!queryStream) {
183 cerr << "Cannot open query file\n";
184 exit(1);
185 }
186 queryIn = &queryStream; // make this query stream
187 }
188 else { // illegal syntax
189 cerr << "Unrecognized option.\n";
190 exit(1);
191 }
192 i++;
193 }
194 if (dataIn == NULL || queryIn == NULL) {
195 cerr << "-df and -qf options must be specified\n";
196 exit(1);
197 }
198 }