nn.h
00001 /*
00002 Copyright (c) 2004, Tim Bailey
00003 All rights reserved.
00004 
00005 Redistribution and use in source and binary forms, with or without
00006 modification, are permitted provided that the following conditions are met:
00007 
00008     * Redistributions of source code must retain the above copyright notice,
00009       this list of conditions and the following disclaimer.
00010     * Redistributions in binary form must reproduce the above copyright notice,
00011       this list of conditions and the following disclaimer in the documentation
00012       and/or other materials provided with the distribution.
00013     * Neither the name of the Player Project nor the names of its contributors
00014       may be used to endorse or promote products derived from this software
00015       without specific prior written permission.
00016 
00017 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
00018 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00019 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00020 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
00021 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00022 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00023 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
00024 ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00026 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027 */
00028 
00029 
00030 /* Nearest-neighbours algorithm for 2D point-sets.
00031  * Compute the single nearest-neighbour of a point, or the set of k-nearest neighbours.
00032  *
00033  * This is a very simple algorithm that is reasonably efficient for planar
00034  * points. However much faster algorithms are possible.
00035  *
00036  * Tim Bailey 2004.
00037  */
00038 
00039 #ifndef NN_HEADER
00040 #define NN_HEADER
00041 
00042 #include "geometry2D.h"
00043 #include <vector>
00044 
00045 namespace Geom2D {
00046 
00047 // Simple 2D k-nearest-neighbours search
00048 //
00049 class SweepSearch {
00050 public:
00051         enum { NOT_FOUND = -1 };
00052 
00053         SweepSearch(const std::vector<Point> &p, double dmax);
00054 
00055         int query(const Point &q) const;
00056         std::vector<double>& query(const Point &q, std::vector<int> &idx);
00057 
00058 private:        
00059         struct PointIdx { 
00060                 PointIdx() {}
00061                 PointIdx(const Point &p_, const int& i_) : p(p_), i(i_) {}
00062                 Point p;
00063                 int i; 
00064         };
00065 
00066         const double limit;
00067         std::vector<PointIdx> dataset;
00068         std::vector<double> nndists;
00069 
00070         bool is_nearer(double &d2min, int &idxmin, const Point &q, const PointIdx &pi) const;
00071 
00072         bool insert_neighbour(const Point &q, const PointIdx &pi, 
00073                 std::vector<double> &nndists, std::vector<int> &idx);
00074 
00075         static bool yorder (const PointIdx& p, const PointIdx& q) {
00076                 return p.p.y < q.p.y;
00077         }
00078 };
00079 
00080 }
00081 
00082 #endif

Last updated 12 September 2005 21:38:45