00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
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
00086
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
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
00104 if (minDist[j] > maxDist)
00105 {
00106 ind = j;
00107 maxDist = minDist[j];
00108 }
00109 }
00110
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