ompl/datastructures/GreedyKCenters.h
00001 /********************************************************************* 00002 * Software License Agreement (BSD License) 00003 * 00004 * Copyright (c) 2011, Rice University 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 Rice University 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: Mark Moll */ 00036 00037 #ifndef OMPL_DATASTRUCTURES_GREEDY_K_CENTERS_ 00038 #define OMPL_DATASTRUCTURES_GREEDY_K_CENTERS_ 00039 00040 #include "ompl/util/RandomNumbers.h" 00041 00042 namespace ompl 00043 { 00047 template<typename _T> 00048 class GreedyKCenters 00049 { 00050 public: 00052 typedef boost::function<double(const _T&, const _T&)> DistanceFunction; 00053 00054 GreedyKCenters() 00055 { 00056 } 00057 00058 virtual ~GreedyKCenters() 00059 { 00060 } 00061 00063 void setDistanceFunction(const DistanceFunction &distFun) 00064 { 00065 distFun_ = distFun; 00066 } 00067 00069 const DistanceFunction& getDistanceFunction() const 00070 { 00071 return distFun_; 00072 } 00073 00082 void kcenters(const std::vector<_T>& data, unsigned int k, 00083 std::vector<unsigned int>& centers, std::vector<std::vector<double> >& dists) 00084 { 00085 // array containing the minimum distance between each data point 00086 // and the centers computed so far 00087 std::vector<double> minDist(data.size(), std::numeric_limits<double>::infinity()); 00088 00089 centers.clear(); 00090 centers.reserve(k); 00091 dists.resize(data.size(), std::vector<double>(k)); 00092 // first center is picked randomly 00093 centers.push_back(rng_.uniformInt(0, data.size() - 1)); 00094 for (unsigned i=1; i<k; ++i) 00095 { 00096 unsigned ind; 00097 const _T& center = data[centers[i - 1]]; 00098 double maxDist = -std::numeric_limits<double>::infinity(); 00099 for (unsigned j=0; j<data.size(); ++j) 00100 { 00101 if ((dists[j][i-1] = distFun_(data[j], center)) < minDist[j]) 00102 minDist[j] = dists[j][i - 1]; 00103 // the j-th center is the one furthest away from center 0,..,j-1 00104 if (minDist[j] > maxDist) 00105 { 00106 ind = j; 00107 maxDist = minDist[j]; 00108 } 00109 } 00110 // no more centers available 00111 if (maxDist < std::numeric_limits<double>::epsilon()) break; 00112 centers.push_back(ind); 00113 } 00114 00115 const _T& center = data[centers.back()]; 00116 unsigned i = centers.size() - 1; 00117 for (unsigned j = 0; j < data.size(); ++j) 00118 dists[j][i] = distFun_(data[j], center); 00119 } 00120 00121 protected: 00123 DistanceFunction distFun_; 00124 00126 RNG rng_; 00127 }; 00128 } 00129 00130 #endif