Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #include "nabo/nabo.h"
00033 #include <iostream>
00034 #include <fstream>
00035 #include <stdexcept>
00036
00037 using namespace std;
00038 using namespace Nabo;
00039
00040 template<typename T>
00041 typename NearestNeighbourSearch<T>::Matrix load(const char *fileName)
00042 {
00043 typedef typename NearestNeighbourSearch<T>::Matrix Matrix;
00044
00045 ifstream ifs(fileName);
00046 if (!ifs.good())
00047 throw runtime_error(string("Cannot open file ") + fileName);
00048
00049 vector<T> data;
00050 int dim(0);
00051 bool firstLine(true);
00052
00053 while (!ifs.eof())
00054 {
00055 char line[1024];
00056 ifs.getline(line, sizeof(line));
00057 line[sizeof(line)-1] = 0;
00058
00059 char *token = strtok(line, " \t,;");
00060 while (token)
00061 {
00062 if (firstLine)
00063 ++dim;
00064 data.push_back(atof(token));
00065
00066 token = strtok(NULL, " \t,;");
00067 }
00068 firstLine = false;
00069 }
00070
00071 return Matrix::Map(&data[0], dim, data.size() / dim);
00072 }
00073
00074 template<typename T>
00075 void dumpCoordinateForSVG(const typename NearestNeighbourSearch<T>::Vector coord, const float zoom = 1, const float ptSize = 1, const char* style = "stroke=\"black\" fill=\"red\"")
00076 {
00077 if (coord.size() == 2)
00078 cout
00079 << "<circle cx=\"" << zoom*coord(0)
00080 << "\" cy=\"" << zoom*coord(1)
00081 << "\" r=\"" << ptSize
00082 << "\" stroke-width=\"" << 0.2 * ptSize
00083 << "\" " << style << "/>" << endl;
00084 else
00085 assert(false);
00086 }
00087
00088 int main(int argc, char* argv[])
00089 {
00090 typedef Nabo::NearestNeighbourSearch<float>::Matrix Matrix;
00091 typedef Nabo::NearestNeighbourSearch<float>::Vector Vector;
00092 typedef Nabo::NearestNeighbourSearch<float>::Index Index;
00093 typedef Nabo::NearestNeighbourSearch<float>::Indexes Indexes;
00094 typedef Nabo::BruteForceSearch<float> BFSF;
00095 typedef Nabo::KDTree<float> KDTF;
00096
00097 if (argc != 2)
00098 {
00099 cerr << "Usage " << argv[0] << " DATA" << endl;
00100 return 1;
00101 }
00102
00103 Matrix d(load<float>(argv[1]));
00104 BFSF bfs(d);
00105 KDTF kdt(d);
00106 const Index K(10);
00107
00108
00109 if (K >= d.size())
00110 return 2;
00111 const int itCount(100);
00112 for (int i = 0; i < itCount; ++i)
00113 {
00114
00115
00116
00117 Vector q(d.col(rand() % d.cols()));
00118 q.cwise() += 0.01;
00119
00120 Indexes indexes_bf(bfs.knn(q, K, false));
00121
00122 Indexes indexes_kdtree(kdt.knn(q, K, false));
00123
00124 if (ndexes_bf.size() != indexes_kdtree.size())
00125 return 2;
00126 assert(indexes_bf.size() == indexes_kdtree.size());
00127 assert(indexes_bf.size() == K);
00128
00129 for (size_t j = 0; j < K; ++j)
00130 {
00131 Vector pbf(d.col(indexes_bf[j]));
00132 Vector pkdtree(d.col(indexes_kdtree[j]));
00133
00134
00135 assert(indexes_bf[j] == indexes_kdtree[j]);
00136 assert(dist2(pbf, pkdtree) < numeric_limits<float>::epsilon());
00137 }
00138 }
00139 cerr << "stats kdtree: "
00140 << kdt.getStatistics().totalVisitCount << " on "
00141 << itCount * d.cols() << " ("
00142 << double(100 * kdt.getStatistics().totalVisitCount) / double(itCount * d.cols()) << " %"
00143 << ")" << endl;
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166 return 0;
00167 }