nn.h

00001 /* Nearest-neighbours algorithm for 2D point-sets.
00002  * Compute the single nearest-neighbour of a point, or the set of k-nearest neighbours.
00003  *
00004  * This is a very simple algorithm that is reasonably efficient for planar
00005  * points. However much faster algorithms are possible.
00006  *
00007  * Tim Bailey 2004.
00008  */
00009 
00010 #ifndef NN_HEADER
00011 #define NN_HEADER
00012 
00013 #include "geometry2D.h"
00014 #include <vector>
00015 
00016 namespace Geom2D {
00017 
00018 // Simple 2D k-nearest-neighbours search
00019 //
00020 class SweepSearch {
00021 public:
00022         enum { NOT_FOUND = -1 };
00023 
00024         SweepSearch(const std::vector<Point> &p, double dmax);
00025 
00026         int query(const Point &q) const;
00027         std::vector<double>& query(const Point &q, std::vector<int> &idx);
00028 
00029 private:        
00030         struct PointIdx { 
00031                 PointIdx() {}
00032                 PointIdx(const Point &p_, const int& i_) : p(p_), i(i_) {}
00033                 Point p;
00034                 int i; 
00035         };
00036 
00037         const double limit;
00038         std::vector<PointIdx> dataset;
00039         std::vector<double> nndists;
00040 
00041         bool is_nearer(double &d2min, int &idxmin, const Point &q, const PointIdx &pi) const;
00042 
00043         bool insert_neighbour(const Point &q, const PointIdx &pi, 
00044                 std::vector<double> &nndists, std::vector<int> &idx);
00045 
00046         static bool yorder (const PointIdx& p, const PointIdx& q) {
00047                 return p.p.y < q.p.y;
00048         }
00049 };
00050 
00051 }
00052 
00053 #endif

Last updated 12 September 2005 21:38:45