NearestNeighborsSqrtApprox.h
Go to the documentation of this file.00001 /********************************************************************* 00002 * Software License Agreement (BSD License) 00003 * 00004 * Copyright (c) 2008, Willow Garage, Inc. 00005 * All rights reserved. 00006 * 00007 * Redistribution and use in source and binary forms, with or without 00008 * modification, are permitted provided that the following conditions 00009 * are met: 00010 * 00011 * * Redistributions of source code must retain the above copyright 00012 * notice, this list of conditions and the following disclaimer. 00013 * * Redistributions in binary form must reproduce the above 00014 * copyright notice, this list of conditions and the following 00015 * disclaimer in the documentation and/or other materials provided 00016 * with the distribution. 00017 * * Neither the name of the Willow Garage nor the names of its 00018 * contributors may be used to endorse or promote products derived 00019 * from this software without specific prior written permission. 00020 * 00021 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00022 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00023 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 00024 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 00025 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 00026 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 00027 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 00028 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 00029 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00030 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 00031 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00032 * POSSIBILITY OF SUCH DAMAGE. 00033 *********************************************************************/ 00034 00035 /* Author: Ioan Sucan */ 00036 00037 #ifndef OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_SQRT_APPROX_ 00038 #define OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_SQRT_APPROX_ 00039 00040 #include "ompl/datastructures/NearestNeighborsLinear.h" 00041 #include <algorithm> 00042 #include <cmath> 00043 00044 namespace ompl 00045 { 00056 template<typename _T> 00057 class NearestNeighborsSqrtApprox : public NearestNeighborsLinear<_T> 00058 { 00059 public: 00060 NearestNeighborsSqrtApprox(void) : NearestNeighborsLinear<_T>(), checks_(0), offset_(0) 00061 { 00062 } 00063 00064 virtual ~NearestNeighborsSqrtApprox(void) 00065 { 00066 } 00067 00068 virtual void clear(void) 00069 { 00070 NearestNeighborsLinear<_T>::clear(); 00071 checks_ = 0; 00072 offset_ = 0; 00073 } 00074 00075 virtual void add(_T &data) 00076 { 00077 NearestNeighborsLinear<_T>::add(data); 00078 updateCheckCount(); 00079 } 00080 00081 virtual void add(std::vector<_T> &data) 00082 { 00083 NearestNeighborsLinear<_T>::add(data); 00084 updateCheckCount(); 00085 } 00086 00087 virtual bool remove(_T &data) 00088 { 00089 bool result = NearestNeighborsLinear<_T>::remove(data); 00090 if (result) 00091 updateCheckCount(); 00092 return result; 00093 } 00094 00095 virtual _T nearest(const _T &data) const 00096 { 00097 const std::size_t n = NearestNeighborsLinear<_T>::data_.size(); 00098 std::size_t pos = n; 00099 00100 if (checks_ > 0 && n > 0) 00101 { 00102 double dmin = 0.0; 00103 for (std::size_t j = 0 ; j < checks_ ; ++j) 00104 { 00105 std::size_t i = (j * checks_ + offset_) % n; 00106 00107 double distance = NearestNeighbors<_T>::distFun_(NearestNeighborsLinear<_T>::data_[i], data); 00108 if (pos == n || dmin > distance) 00109 { 00110 pos = i; 00111 dmin = distance; 00112 } 00113 } 00114 offset_ = (offset_ + 1) % checks_; 00115 } 00116 if (pos != n) 00117 return NearestNeighborsLinear<_T>::data_[pos]; 00118 00119 throw Exception("No elements found"); 00120 } 00121 00122 protected: 00123 00124 inline 00125 void updateCheckCount(void) 00126 { 00127 checks_ = 1 + (std::size_t)floor(sqrt((double)NearestNeighborsLinear<_T>::data_.size())); 00128 } 00129 00131 std::size_t checks_; 00132 00134 mutable std::size_t offset_; 00135 00136 }; 00137 00138 } 00139 00140 #endif