37 #ifndef OMPL_DATASTRUCTURES_GREEDY_K_CENTERS_
38 #define OMPL_DATASTRUCTURES_GREEDY_K_CENTERS_
40 #include "ompl/util/RandomNumbers.h"
82 void kcenters(
const std::vector<_T>& data,
unsigned int k,
83 std::vector<unsigned int>& centers, std::vector<std::vector<double> >& dists)
87 std::vector<double> minDist(data.size(), std::numeric_limits<double>::infinity());
91 dists.resize(data.size(), std::vector<double>(k));
94 for (
unsigned i=1; i<k; ++i)
97 const _T& center = data[centers[i - 1]];
98 double maxDist = -std::numeric_limits<double>::infinity();
99 for (
unsigned j=0; j<data.size(); ++j)
101 if ((dists[j][i-1] =
distFun_(data[j], center)) < minDist[j])
102 minDist[j] = dists[j][i - 1];
104 if (minDist[j] > maxDist)
107 maxDist = minDist[j];
111 if (maxDist < std::numeric_limits<double>::epsilon())
break;
112 centers.push_back(ind);
115 const _T& center = data[centers.back()];
116 unsigned i = centers.size() - 1;
117 for (
unsigned j = 0; j < data.size(); ++j)
118 dists[j][i] =
distFun_(data[j], center);
DistanceFunction distFun_
The used distance function.
An instance of this class can be used to greedily select a given number of representatives from a set...
const DistanceFunction & getDistanceFunction(void) const
Get the distance function used.
boost::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.
void kcenters(const std::vector< _T > &data, unsigned int k, std::vector< unsigned int > ¢ers, std::vector< std::vector< double > > &dists)
Greedy algorithm for selecting k centers.
int uniformInt(int lower_bound, int upper_bound)
Generate a random integer within given bounds: [lower_bound, upper_bound].