All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator
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::function2<double, const _T&, const _T&> DistanceFunction;
00053 
00054         GreedyKCenters(void)
00055         {
00056         }
00057 
00058         virtual ~GreedyKCenters(void)
00059         {
00060         }
00061 
00063         void setDistanceFunction(const DistanceFunction &distFun)
00064         {
00065             distFun_ = distFun;
00066         }
00067 
00069         const DistanceFunction& getDistanceFunction(void) 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