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
|
#pragma once
#include <mapbox/geojsonvt/types.hpp>
namespace mapbox {
namespace geojsonvt {
namespace detail {
// square distance from a point to a segment
inline double getSqSegDist(const vt_point& p, const vt_point& a, const vt_point& b) {
double x = a.x;
double y = a.y;
double dx = b.x - a.x;
double dy = b.y - a.y;
if ((dx != 0.0) || (dy != 0.0)) {
const double t = ((p.x - a.x) * dx + (p.y - a.y) * dy) / (dx * dx + dy * dy);
if (t > 1) {
x = b.x;
y = b.y;
} else if (t > 0) {
x += dx * t;
y += dy * t;
}
}
dx = p.x - x;
dy = p.y - y;
return dx * dx + dy * dy;
}
// calculate simplification data using optimized Douglas-Peucker algorithm
inline void simplify(std::vector<vt_point>& points, size_t first, size_t last, double sqTolerance) {
double maxSqDist = sqTolerance;
size_t index = 0;
for (auto i = first + 1; i < last; i++) {
const double sqDist = getSqSegDist(points[i], points[first], points[last]);
if (sqDist > maxSqDist) {
index = i;
maxSqDist = sqDist;
}
}
if (maxSqDist > sqTolerance) {
// save the point importance in squared pixels as a z coordinate
points[index].z = maxSqDist;
if (index - first > 1)
simplify(points, first, index, sqTolerance);
if (last - index > 1)
simplify(points, index, last, sqTolerance);
}
}
inline void simplify(std::vector<vt_point>& points, double tolerance) {
const size_t len = points.size();
// always retain the endpoints (1 is the max value)
points[0].z = 1.0;
points[len - 1].z = 1.0;
simplify(points, 0, len - 1, tolerance * tolerance);
}
} // namespace detail
} // namespace geojsonvt
} // namespace mapbox
|
