ChainApproximation.cpp
Go to the documentation of this file.
1 #include "ChainApproximation.h"
2 
3 #include <iterator>
4 #include <numeric>
5 
6 #include <Eigen/Geometry>
7 #include <SimoxUtility/algorithm/apply.hpp>
8 
11 
12 #include "range/v3/algorithm/find.hpp"
13 #include "range/v3/numeric/iota.hpp"
14 
16 {
17 
18  ChainApproximation::ChainApproximation(const Points& points, const Params& params) :
19  points(points), params(params)
20  {
21  // fill indices
22  indices.resize(points.size());
23  ranges::iota(indices, 0);
24  }
25 
28  {
29 
30  int iterations = 0;
31 
32  const auto maxIterConditionReached = [&]()
33  {
34  // inactive?
35  if (params.maxIterations <= 0)
36  {
37  return false;
38  }
39 
40  return iterations >= params.maxIterations;
41  };
42 
43  while (true)
44  {
45  if (maxIterConditionReached())
46  {
47  return ApproximationResult{
49  .iterations = iterations};
50  }
51 
52  if (not approximateStep())
53  {
54  return ApproximationResult{
56  .iterations = iterations,
57  .reductionFactor = 1.F - static_cast<float>(indices.size()) /
58  static_cast<float>(points.size())};
59  }
60 
61  iterations++;
62  }
63  }
64 
65  ChainApproximation::Triplets
66  ChainApproximation::getTriplets() const
67  {
68  const int nIndices = static_cast<int>(indices.size());
69 
70  if (nIndices < 3)
71  {
72  return {};
73  }
74 
75  Triplets triplets;
76  triplets.reserve(indices.size());
77 
78  // Here, we iterate over all elements under consideration.
79  // The aim is to create a view - a sliding window - over the
80  // indices. i will always point to the centered element.
81 
82  // the first element
83  triplets.emplace_back(indices.back(), indices.front(), indices.at(1));
84 
85  // intermediate elements
86  for (int i = 1; i < (nIndices - 1); i++)
87  {
88  triplets.emplace_back(indices.at(i - 1), indices.at(i), indices.at(i + 1));
89  }
90 
91  // the last element
92  triplets.emplace_back(indices.back(), indices.front(), indices.at(1));
93 
94  return triplets;
95  }
96 
97  std::vector<float>
98  ChainApproximation::computeDistances(const ChainApproximation::Triplets& triplets)
99  {
100  std::vector<float> distances;
101  distances.reserve(triplets.size());
102 
103  std::transform(triplets.begin(),
104  triplets.end(),
105  std::back_inserter(distances),
106  [&](const auto& triplet) { return computeDistance(triplet); });
107 
108  return distances;
109  }
110  float
111  ChainApproximation::computeDistance(const ChainApproximation::Triplet& triplet) const
112  {
113  using Line = Eigen::ParametrizedLine<float, 2>;
114 
115  const Eigen::Vector2f& ptBefore = points.at(triplet.a);
116  const Eigen::Vector2f& ptPivot = points.at(triplet.b);
117  const Eigen::Vector2f& ptAfter = points.at(triplet.c);
118 
119  const auto line = Line::Through(ptBefore, ptAfter);
120  return line.distance(ptPivot);
121  }
122 
123  bool
124  ChainApproximation::approximateStep()
125  {
126  const size_t nIndices = indices.size();
127  if (nIndices <= 3)
128  {
129  return false;
130  }
131 
132  const Triplets triplets = getTriplets();
133  const std::vector<float> distances = computeDistances(triplets);
134 
135  ARMARX_CHECK_EQUAL(triplets.size(), distances.size());
136  const int n = static_cast<int>(triplets.size());
137 
138  std::vector<int> indicesToBeRemoved;
139 
140  // TODO(fabian.reister): consider boundaries
141  for (int i = 1; i < n - 1; i++)
142  {
143  const auto& distance = distances.at(i);
144 
145  // check distance criterion (necessary conditio)
146  if (distance >= params.distanceTh)
147  {
148  continue;
149  }
150 
151  // better remove this element than those left and right (sufficient condition)
152  if (distance <= std::min(distances.at(i - 1), distances.at(i + 1)))
153  {
154  indicesToBeRemoved.emplace_back(triplets.at(i).b);
155  }
156  }
157 
158  // termination condition
159  if (indicesToBeRemoved.empty())
160  {
161  return false;
162  }
163 
164  const auto isMatch = [&](const int& idx) -> bool
165  { return ranges::find(indicesToBeRemoved, idx) != indicesToBeRemoved.end(); };
166 
167  indices.erase(std::remove_if(indices.begin(), indices.end(), isMatch), indices.end());
168 
169  return true;
170  }
173  {
174  return simox::alg::apply(indices, [&](const auto& idx) { return points.at(idx); });
175  }
176 
177  std::ostream&
178  detail::operator<<(std::ostream& str, const ApproximationResult& res)
179  {
180  using TerminationCondition = ApproximationResult::TerminationCondition;
181 
182  const std::string condStr = [&res]() -> std::string
183  {
184  std::string repr;
185 
186  switch (res.condition)
187  {
188  case TerminationCondition::Converged:
189  repr = "Converged";
190  break;
191  case TerminationCondition::IterationLimit:
192  repr = "IterationLimit";
193  break;
194  }
195  return repr;
196  }();
197 
198  str << "ApproximationResult: ["
199  << "condition: " << condStr << " | "
200  << "iterations: " << res.iterations << " | "
201  << "reduction: " << res.reductionFactor * 100 << "%]";
202 
203  return str;
204  }
205 } // namespace armarx::navigation::algorithm
ChainApproximation.h
str
std::string str(const T &t)
Definition: UserAssistedSegmenterGuiWidgetController.cpp:42
armarx::navigation::algorithm::detail::ChainApproximationParams::maxIterations
int maxIterations
Definition: ChainApproximation.h:36
LocalException.h
armarx::navigation::algorithm::detail::ChainApproximationParams
Definition: ChainApproximation.h:32
armarx::navigation::algorithm::ChainApproximation::approximate
ApproximationResult approximate()
Definition: ChainApproximation.cpp:27
armarx::navigation::algorithm::detail::ApproximationResult::condition
TerminationCondition condition
Definition: ChainApproximation.h:46
armarx::navigation::algorithm::ChainApproximation::approximatedChain
Points approximatedChain() const
Definition: ChainApproximation.cpp:172
armarx::navigation::algorithm::detail::ApproximationResult::TerminationCondition::IterationLimit
@ IterationLimit
armarx::navigation::algorithm::detail::ApproximationResult::iterations
int iterations
Definition: ChainApproximation.h:48
armarx::navigation::algorithm::ChainApproximation::Points
std::vector< Point > Points
Definition: ChainApproximation.h:60
armarx::navigation::algorithm
This file is part of ArmarX.
Definition: AStarPlanner.cpp:29
armarx::navigation::algorithm::detail::operator<<
std::ostream & operator<<(std::ostream &str, const ApproximationResult &res)
Definition: ChainApproximation.cpp:178
armarx::navigation::algorithm::ChainApproximation::ChainApproximation
ChainApproximation(const Points &points, const Params &params)
Definition: ChainApproximation.cpp:18
ExpressionException.h
armarx::navigation::algorithm::detail::ChainApproximationParams::distanceTh
float distanceTh
Definition: ChainApproximation.h:34
armarx::transform
auto transform(const Container< InputT, Alloc > &in, OutputT(*func)(InputT const &)) -> Container< OutputT, typename std::allocator_traits< Alloc >::template rebind_alloc< OutputT > >
Convenience function (with less typing) to transform a container of type InputT into the same contain...
Definition: algorithm.h:315
armarx::navigation::algorithm::detail::ApproximationResult::TerminationCondition::Converged
@ Converged
distance
double distance(const Point &a, const Point &b)
Definition: point.hpp:88
min
T min(T t1, T t2)
Definition: gdiam.h:42
ARMARX_CHECK_EQUAL
#define ARMARX_CHECK_EQUAL(lhs, rhs)
This macro evaluates whether lhs is equal (==) rhs and if it turns out to be false it will throw an E...
Definition: ExpressionException.h:130
armarx::navigation::algorithm::detail::ApproximationResult::reductionFactor
float reductionFactor
Definition: ChainApproximation.h:50
armarx::navigation::algorithm::detail::ApproximationResult::TerminationCondition
TerminationCondition
Definition: ChainApproximation.h:41
armarx::navigation::algorithm::detail::ApproximationResult
Definition: ChainApproximation.h:39
Line
Eigen::ParametrizedLine< float, 2 > Line
Definition: LaserScannerSelfLocalisation.cpp:51