brute.cpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------
00002 // File:                        brute.cpp
00003 // Programmer:          Sunil Arya and David Mount
00004 // Description:         Brute-force nearest neighbors
00005 // Last modified:       05/03/05 (Version 1.1)
00006 //----------------------------------------------------------------------
00007 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
00008 // David Mount.  All Rights Reserved.
00009 // 
00010 // This software and related documentation is part of the Approximate
00011 // Nearest Neighbor Library (ANN).  This software is provided under
00012 // the provisions of the Lesser GNU Public License (LGPL).  See the
00013 // file ../ReadMe.txt for further information.
00014 // 
00015 // The University of Maryland (U.M.) and the authors make no
00016 // representations about the suitability or fitness of this software for
00017 // any purpose.  It is provided "as is" without express or implied
00018 // warranty.
00019 //----------------------------------------------------------------------
00020 // History:
00021 //      Revision 0.1  03/04/98
00022 //              Initial release
00023 //      Revision 1.1  05/03/05
00024 //              Added fixed-radius kNN search
00025 //----------------------------------------------------------------------
00026 
00027 #include <ANN/ANNx.h>                                   // all ANN includes
00028 #include "pr_queue_k.h"                                 // k element priority queue
00029 
00030 //----------------------------------------------------------------------
00031 //              Brute-force search simply stores a pointer to the list of
00032 //              data points and searches linearly for the nearest neighbor.
00033 //              The k nearest neighbors are stored in a k-element priority
00034 //              queue (which is implemented in a pretty dumb way as well).
00035 //
00036 //              If ANN_ALLOW_SELF_MATCH is ANNfalse then data points at distance
00037 //              zero are not considered.
00038 //
00039 //              Note that the error bound eps is passed in, but it is ignored.
00040 //              These routines compute exact nearest neighbors (which is needed
00041 //              for validation purposes in ann_test.cpp).
00042 //----------------------------------------------------------------------
00043 
00044 ANNbruteForce::ANNbruteForce(                   // constructor from point array
00045         ANNpointArray           pa,                             // point array
00046         int                                     n,                              // number of points
00047         int                                     dd)                             // dimension
00048 {
00049         dim = dd;  n_pts = n;  pts = pa;
00050 }
00051 
00052 ANNbruteForce::~ANNbruteForce() { }             // destructor (empty)
00053 
00054 void ANNbruteForce::annkSearch(                 // approx k near neighbor search
00055         ANNpoint                        q,                              // query point
00056         int                                     k,                              // number of near neighbors to return
00057         ANNidxArray                     nn_idx,                 // nearest neighbor indices (returned)
00058         ANNdistArray            dd,                             // dist to near neighbors (returned)
00059         double                          eps)                    // error bound (ignored)
00060 {
00061         ANNmin_k mk(k);                                         // construct a k-limited priority queue
00062         int i;
00063 
00064         if (k > n_pts) {                                        // too many near neighbors?
00065                 annError("Requesting more near neighbors than data points", ANNabort);
00066         }
00067                                                                                 // run every point through queue
00068         for (i = 0; i < n_pts; i++) {
00069                                                                                 // compute distance to point
00070                 ANNdist sqDist = annDist(dim, pts[i], q);
00071                 if (ANN_ALLOW_SELF_MATCH || sqDist != 0)
00072                         mk.insert(sqDist, i);
00073         }
00074         for (i = 0; i < k; i++) {                       // extract the k closest points
00075                 dd[i] = mk.ith_smallest_key(i);
00076                 nn_idx[i] = mk.ith_smallest_info(i);
00077         }
00078 }
00079 
00080 int ANNbruteForce::annkFRSearch(                // approx fixed-radius kNN search
00081         ANNpoint                        q,                              // query point
00082         ANNdist                         sqRad,                  // squared radius
00083         int                                     k,                              // number of near neighbors to return
00084         ANNidxArray                     nn_idx,                 // nearest neighbor array (returned)
00085         ANNdistArray            dd,                             // dist to near neighbors (returned)
00086         double                          eps)                    // error bound
00087 {
00088         ANNmin_k mk(k);                                         // construct a k-limited priority queue
00089         int i;
00090         int pts_in_range = 0;                           // number of points in query range
00091                                                                                 // run every point through queue
00092         for (i = 0; i < n_pts; i++) {
00093                                                                                 // compute distance to point
00094                 ANNdist sqDist = annDist(dim, pts[i], q);
00095                 if (sqDist <= sqRad &&                  // within radius bound
00096                         (ANN_ALLOW_SELF_MATCH || sqDist != 0)) { // ...and no self match
00097                         mk.insert(sqDist, i);
00098                         pts_in_range++;
00099                 }
00100         }
00101         for (i = 0; i < k; i++) {                       // extract the k closest points
00102                 if (dd != NULL)
00103                         dd[i] = mk.ith_smallest_key(i);
00104                 if (nn_idx != NULL)
00105                         nn_idx[i] = mk.ith_smallest_info(i);
00106         }
00107 
00108         return pts_in_range;
00109 }

Generated on Wed Nov 23 18:59:59 2011 for FreeCAD by  doxygen 1.6.1