Loading...
Searching...
No Matches
GreedyKCenters.h
1/*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2011, Rice University
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the Rice University nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *********************************************************************/
34
35/* Author: Mark Moll */
36
37#ifndef OMPL_DATASTRUCTURES_GREEDY_K_CENTERS_
38#define OMPL_DATASTRUCTURES_GREEDY_K_CENTERS_
39
40#include "ompl/util/RandomNumbers.h"
41#include <functional>
42#include <Eigen/Core>
43
44namespace ompl
45{
49 template <typename _T>
50 class GreedyKCenters
51 {
52 public:
54 using DistanceFunction = std::function<double(const _T &, const _T &)>;
56 using Matrix = Eigen::MatrixXd;
57
58 GreedyKCenters() = default;
59
60 virtual ~GreedyKCenters() = default;
61
64 {
65 distFun_ = distFun;
66 }
67
70 {
71 return distFun_;
72 }
73
82 void kcenters(const std::vector<_T> &data, unsigned int k, std::vector<unsigned int> &centers, Matrix &dists)
83 {
84 // array containing the minimum distance between each data point
85 // and the centers computed so far
86 std::vector<double> minDist(data.size(), std::numeric_limits<double>::infinity());
87
88 centers.clear();
89 centers.reserve(k);
90 if ((std::size_t)dists.rows() < data.size() || (std::size_t)dists.cols() < k)
91 dists.resize(std::max(2u * (std::size_t)dists.rows() + 1u, data.size()), k);
92 // first center is picked randomly
93 centers.push_back(rng_.uniformInt(0, data.size() - 1));
94 for (unsigned i = 1; i < k; ++i)
95 {
96 unsigned ind = 0;
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)
100 {
101 if ((dists(j, i - 1) = distFun_(data[j], center)) < minDist[j])
102 minDist[j] = dists(j, i - 1);
103 // the j-th center is the one furthest away from center 0,..,j-1
104 if (minDist[j] > maxDist)
105 {
106 ind = j;
107 maxDist = minDist[j];
108 }
109 }
110 // no more centers available
111 if (maxDist < std::numeric_limits<double>::epsilon())
112 break;
113 centers.push_back(ind);
114 }
115
116 const _T &center = data[centers.back()];
117 unsigned i = centers.size() - 1;
118 for (unsigned j = 0; j < data.size(); ++j)
119 dists(j, i) = distFun_(data[j], center);
120 }
121
122 protected:
125
128 };
129} // namespace ompl
130
131#endif
DistanceFunction distFun_
The used distance function.
std::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.
void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.
const DistanceFunction & getDistanceFunction() const
Get the distance function used.
void kcenters(const std::vector< _T > &data, unsigned int k, std::vector< unsigned int > &centers, Matrix &dists)
Greedy algorithm for selecting k centers.
Eigen::MatrixXd Matrix
A matrix type for storing distances between points and centers.
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
Main namespace. Contains everything in this library.