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