1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
#pragma once
#include "geometry/point2d.hpp"
#include "base/base.hpp"
#include "base/logging.hpp"
#include "base/stl_helpers.hpp"
#include <algorithm>
#include <cstdint>
#include <iterator>
#include <utility>
#include <vector>
// Polyline simplification algorithms.
//
// SimplifyXXX() should be used to simplify polyline for a given epsilon.
// (!) They do not include the last point to the simplification, the calling side should do it.
namespace impl
{
///@name This functions take input range NOT like STL does: [first, last].
//@{
template <typename DistanceFn, typename Iter>
std::pair<double, Iter> MaxDistance(Iter first, Iter last, DistanceFn & distFn)
{
std::pair<double, Iter> res(0.0, last);
if (std::distance(first, last) <= 1)
return res;
for (Iter i = first + 1; i != last; ++i)
{
double const d = distFn(m2::PointD(*first), m2::PointD(*last), m2::PointD(*i));
if (res.first < d)
{
res.first = d;
res.second = i;
}
}
return res;
}
// Actual SimplifyDP implementation.
template <typename DistanceFn, typename Iter, typename Out>
void SimplifyDP(Iter first, Iter last, double epsilon, DistanceFn & distFn, Out & out)
{
std::pair<double, Iter> maxDist = impl::MaxDistance(first, last, distFn);
if (maxDist.second == last || maxDist.first < epsilon)
{
out(*last);
}
else
{
impl::SimplifyDP(first, maxDist.second, epsilon, distFn, out);
impl::SimplifyDP(maxDist.second, last, epsilon, distFn, out);
}
}
//@}
struct SimplifyOptimalRes
{
SimplifyOptimalRes() : m_PointCount(-1U) {}
SimplifyOptimalRes(int32_t nextPoint, uint32_t pointCount)
: m_NextPoint(nextPoint), m_PointCount(pointCount) {}
int32_t m_NextPoint;
uint32_t m_PointCount;
};
} // namespace impl
// Douglas-Peucker algorithm for STL-like range [beg, end).
// Iteratively includes the point with max distance from the current simplification.
// Average O(n log n), worst case O(n^2).
template <typename DistanceFn, typename Iter, typename Out>
void SimplifyDP(Iter beg, Iter end, double epsilon, DistanceFn distFn, Out out)
{
if (beg != end)
{
out(*beg);
impl::SimplifyDP(beg, end - 1, epsilon, distFn, out);
}
}
// Dynamic programming near-optimal simplification.
// Uses O(n) additional memory.
// Worst case O(n^3) performance, average O(n*k^2), where k is maxFalseLookAhead - parameter,
// which limits the number of points to try, that produce error > epsilon.
// Essentially, it's a trade-off between optimality and performance.
// Values around 20 - 200 are reasonable.
template <typename DistanceFn, typename Iter, typename Out>
void SimplifyNearOptimal(int maxFalseLookAhead, Iter beg, Iter end, double epsilon,
DistanceFn distFn, Out out)
{
int32_t const n = static_cast<int32_t>(end - beg);
if (n <= 2)
{
for (Iter it = beg; it != end; ++it)
out(*it);
return;
}
std::vector<impl::SimplifyOptimalRes> F(n);
F[n - 1] = impl::SimplifyOptimalRes(n, 1);
for (int32_t i = n - 2; i >= 0; --i)
{
for (int32_t falseCount = 0, j = i + 1; j < n && falseCount < maxFalseLookAhead; ++j)
{
uint32_t const newPointCount = F[j].m_PointCount + 1;
if (newPointCount < F[i].m_PointCount)
{
if (impl::MaxDistance(beg + i, beg + j, distFn).first < epsilon)
{
F[i].m_NextPoint = j;
F[i].m_PointCount = newPointCount;
}
else
{
++falseCount;
}
}
}
}
for (int32_t i = 0; i < n; i = F[i].m_NextPoint)
out(*(beg + i));
}
// Additional points filter to use in simplification.
// SimplifyDP can produce points that define degenerate triangle.
template <typename DistanceFn, typename Point>
class AccumulateSkipSmallTrg
{
public:
AccumulateSkipSmallTrg(DistanceFn & distFn, std::vector<Point> & vec, double eps)
: m_distFn(distFn), m_vec(vec), m_eps(eps)
{
}
void operator()(Point const & p) const
{
// remove points while they make linear triangle with p
size_t count;
while ((count = m_vec.size()) >= 2)
{
auto const a = m2::PointD(m_vec[count - 2]);
auto const b = m2::PointD(p);
auto const c = m2::PointD(m_vec[count - 1]);
if (m_distFn(a, b, c) < m_eps)
m_vec.pop_back();
else
break;
}
m_vec.push_back(p);
}
private:
DistanceFn & m_distFn;
std::vector<Point> & m_vec;
double m_eps;
};
|
