1 | /**************************************************************************** |
2 | ** |
3 | ** Qt adaptation of geosimplify-js |
4 | ** Copyright (C) 2017 Daniel Patterson |
5 | ** See 3rdParty/geosimplify.js for the original license. |
6 | ** |
7 | ** Copyright (C) 2020 Paolo Angelelli <paolo.angelelli@gmail.com> |
8 | ** Copyright (C) 2020 The Qt Company Ltd. |
9 | ** Contact: http://www.qt.io/licensing/ |
10 | ** |
11 | ** This file is part of the QtLocation module of the Qt Toolkit. |
12 | ** |
13 | ** $QT_BEGIN_LICENSE:LGPL3$ |
14 | ** Commercial License Usage |
15 | ** Licensees holding valid commercial Qt licenses may use this file in |
16 | ** accordance with the commercial license agreement provided with the |
17 | ** Software or, alternatively, in accordance with the terms contained in |
18 | ** a written agreement between you and The Qt Company. For licensing terms |
19 | ** and conditions see http://www.qt.io/terms-conditions. For further |
20 | ** information use the contact form at http://www.qt.io/contact-us. |
21 | ** |
22 | ** GNU Lesser General Public License Usage |
23 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
24 | ** General Public License version 3 as published by the Free Software |
25 | ** Foundation and appearing in the file LICENSE.LGPLv3 included in the |
26 | ** packaging of this file. Please review the following information to |
27 | ** ensure the GNU Lesser General Public License version 3 requirements |
28 | ** will be met: https://www.gnu.org/licenses/lgpl.html. |
29 | ** |
30 | ** GNU General Public License Usage |
31 | ** Alternatively, this file may be used under the terms of the GNU |
32 | ** General Public License version 2.0 or later as published by the Free |
33 | ** Software Foundation and appearing in the file LICENSE.GPL included in |
34 | ** the packaging of this file. Please review the following information to |
35 | ** ensure the GNU General Public License version 2.0 requirements will be |
36 | ** met: http://www.gnu.org/licenses/gpl-2.0.html. |
37 | ** |
38 | ** $QT_END_LICENSE$ |
39 | ** |
40 | ****************************************************************************/ |
41 | |
42 | #include "qgeosimplify_p.h" |
43 | #include <QtPositioning/private/qlocationutils_p.h> |
44 | |
45 | QT_BEGIN_NAMESPACE |
46 | |
47 | double QGeoSimplify::getDist(const QGeoCoordinate &p1, const QGeoCoordinate &p2) |
48 | { |
49 | return p1.distanceTo(other: p2); |
50 | } |
51 | |
52 | QDoubleVector2D QGeoSimplify::closestPoint(const QDoubleVector2D &p, const QDoubleVector2D &a, const QDoubleVector2D &b) |
53 | { |
54 | if (a == b) |
55 | return a; |
56 | |
57 | const double u = ((p.x() - a.x()) * (b.x() - a.x()) + (p.y() - a.y()) * (b.y() - a.y()) ) / (b - a).lengthSquared(); |
58 | const QDoubleVector2D intersection(a.x() + u * (b.x() - a.x()) , a.y() + u * (b.y() - a.y()) ); |
59 | QDoubleVector2D candidate = ( (p-a).length() < (p-b).length() ) ? a : b; |
60 | if (u > 0 && u < 1 |
61 | && (p-intersection).length() < (p-candidate).length() ) // And it falls in the segment |
62 | candidate = intersection; |
63 | return candidate; |
64 | } |
65 | |
66 | QGeoCoordinate QGeoSimplify::closestPoint(const QGeoCoordinate &pc, const QGeoCoordinate &ac, const QGeoCoordinate &bc, const double &leftBound) |
67 | { |
68 | QDoubleVector2D p = QWebMercator::coordToMercator(coord: pc); |
69 | if (p.x() < leftBound) |
70 | p.setX(p.x() + leftBound); // unwrap X |
71 | |
72 | QDoubleVector2D a = QWebMercator::coordToMercator(coord: ac); |
73 | if (a.x() < leftBound) |
74 | a.setX(a.x() + leftBound); // unwrap X |
75 | |
76 | QDoubleVector2D b = QWebMercator::coordToMercator(coord: bc); |
77 | if (b.x() < leftBound) |
78 | b.setX(b.x() + leftBound); // unwrap X |
79 | |
80 | QDoubleVector2D intersection = closestPoint(p, a, b); |
81 | if (intersection.x() > 1.0) |
82 | intersection.setX(intersection.x() - leftBound); // wrap X |
83 | |
84 | const QGeoCoordinate closest = QWebMercator::mercatorToCoord(mercator: intersection); |
85 | return closest; |
86 | } |
87 | |
88 | double QGeoSimplify::getSegDist(const QGeoCoordinate &pc, const QGeoCoordinate &ac, const QGeoCoordinate &bc, const double &leftBound) |
89 | { |
90 | const QGeoCoordinate closest = closestPoint(pc, ac, bc, leftBound); |
91 | const double distanceMeters = pc.distanceTo(other: closest); |
92 | return distanceMeters; |
93 | } |
94 | |
95 | double QGeoSimplify::getSegDist(const QDoubleVector2D &p, const QDoubleVector2D &a, const QDoubleVector2D &b, const double &leftBound) |
96 | { |
97 | QDoubleVector2D intersection = closestPoint(p, a, b); |
98 | return getDist(a: intersection, b: p, leftBound); |
99 | } |
100 | |
101 | void QGeoSimplify::simplifyDPStep(const QList<QGeoCoordinate> &points, const double &leftBound, int first, int last, double offsetTolerance, QList<QGeoCoordinate> &simplified) |
102 | { |
103 | double maxDistanceFound = offsetTolerance; |
104 | int index = 0; |
105 | |
106 | for (int i = first + 1; i < last; i++) { |
107 | const double distance = getSegDist(pc: points.at(i), |
108 | ac: points.at(i: first), |
109 | bc: points.at(i: last), |
110 | leftBound); |
111 | |
112 | if (distance > maxDistanceFound) { |
113 | index = i; |
114 | maxDistanceFound = distance; |
115 | } |
116 | } |
117 | |
118 | if (index > 0) { |
119 | if (index - first > 1) |
120 | simplifyDPStep(points, |
121 | leftBound, |
122 | first, |
123 | last: index, |
124 | offsetTolerance, |
125 | simplified); |
126 | simplified.append(t: points.at(i: index)); |
127 | if (last - index > 1) |
128 | simplifyDPStep(points, |
129 | leftBound, |
130 | first: index, |
131 | last, |
132 | offsetTolerance, |
133 | simplified); |
134 | } |
135 | } |
136 | |
137 | double QGeoSimplify::getDist(QDoubleVector2D a, QDoubleVector2D b, const double &leftBound) |
138 | { |
139 | if (a.x() > 1.0) |
140 | a.setX(a.x() - leftBound); // wrap X |
141 | if (b.x() > 1.0) |
142 | b.setX(b.x() - leftBound); // wrap X |
143 | return QWebMercator::mercatorToCoord(mercator: a).distanceTo( |
144 | other: QWebMercator::mercatorToCoord(mercator: b)); |
145 | } |
146 | |
147 | void QGeoSimplify::simplifyDPStep(const QList<QDoubleVector2D> &points, |
148 | const double &leftBound, |
149 | int first, |
150 | int last, |
151 | double offsetTolerance, |
152 | QList<QDoubleVector2D> &simplified) |
153 | { |
154 | double maxDistanceFound = offsetTolerance; |
155 | int index = 0; |
156 | |
157 | for (int i = first + 1; i < last; i++) { |
158 | const double distance = getSegDist(p: points.at(i), |
159 | a: points.at(i: first), |
160 | b: points.at(i: last), |
161 | leftBound); |
162 | |
163 | if (distance > maxDistanceFound) { |
164 | index = i; |
165 | maxDistanceFound = distance; |
166 | } |
167 | } |
168 | |
169 | if (index > 0) { |
170 | if (index - first > 1) |
171 | simplifyDPStep(points, |
172 | leftBound, |
173 | first, |
174 | last: index, |
175 | offsetTolerance, |
176 | simplified); |
177 | simplified.append(t: points.at(i: index)); |
178 | if (last - index > 1) |
179 | simplifyDPStep(points, |
180 | leftBound, |
181 | first: index, |
182 | last, |
183 | offsetTolerance, |
184 | simplified); |
185 | } |
186 | } |
187 | |
188 | static double pixelDistanceAtZoomAndLatitude(int zoom, double latitude) |
189 | { |
190 | const double den = double((1 << (zoom + 8))); |
191 | const double pixelDist = (QLocationUtils::earthMeanCircumference() * |
192 | std::cos(x: QLocationUtils::radians(degrees: latitude))) / den; |
193 | return pixelDist; |
194 | } |
195 | |
196 | static QGeoCoordinate unwrappedToGeo(QDoubleVector2D p, double leftBound) |
197 | { |
198 | if (p.x() > 1.0) |
199 | p.setX(p.x() - leftBound); |
200 | return QWebMercator::mercatorToCoord(mercator: p); |
201 | } |
202 | |
203 | void QGeoSimplify::simplifyDPStepZL(const QList<QDoubleVector2D> &points, |
204 | const double &leftBound, |
205 | int first, |
206 | int last, |
207 | int zoomLevel, |
208 | QList<QDoubleVector2D> &simplified) |
209 | { |
210 | const QGeoCoordinate firstC = unwrappedToGeo(p: points.at(i: first), leftBound); |
211 | const QGeoCoordinate lastC = unwrappedToGeo(p: points.at(i: last), leftBound); |
212 | double maxDistanceFound = (pixelDistanceAtZoomAndLatitude(zoom: zoomLevel, latitude: firstC.latitude()) |
213 | + pixelDistanceAtZoomAndLatitude(zoom: zoomLevel, latitude: lastC.latitude())) * 0.5; |
214 | int index = 0; |
215 | |
216 | for (int i = first + 1; i < last; i++) { |
217 | const double distance = getSegDist(p: points.at(i), |
218 | a: points.at(i: first), |
219 | b: points.at(i: last), |
220 | leftBound); |
221 | |
222 | if (distance > maxDistanceFound) { |
223 | index = i; |
224 | maxDistanceFound = distance; |
225 | } |
226 | } |
227 | |
228 | if (index > 0) { |
229 | if (index - first > 1) |
230 | simplifyDPStepZL(points, |
231 | leftBound, |
232 | first, |
233 | last: index, |
234 | zoomLevel, |
235 | simplified); |
236 | simplified.append(t: points.at(i: index)); |
237 | if (last - index > 1) |
238 | simplifyDPStepZL(points, |
239 | leftBound, |
240 | first: index, |
241 | last, |
242 | zoomLevel, |
243 | simplified); |
244 | } |
245 | } |
246 | |
247 | QList<QGeoCoordinate> QGeoSimplify::simplifyDouglasPeucker(const QList<QGeoCoordinate> &points, |
248 | const double &leftBound, |
249 | double offsetTolerance) { |
250 | const int last = points.size() - 1; |
251 | QList<QGeoCoordinate> simplified { points.first() }; |
252 | simplifyDPStep(points, leftBound, first: 0, last, offsetTolerance, simplified); |
253 | simplified.append(t: points.at(i: last)); |
254 | return simplified; |
255 | } |
256 | |
257 | QList<QDoubleVector2D> QGeoSimplify::simplifyDouglasPeucker(const QList<QDoubleVector2D> &points, |
258 | const double &leftBound, |
259 | double offsetTolerance) { |
260 | const int last = points.size() - 1; |
261 | QList<QDoubleVector2D> simplified { points.first() }; |
262 | simplifyDPStep(points, leftBound, first: 0, last, offsetTolerance, simplified); |
263 | simplified.append(t: points.at(i: last)); |
264 | return simplified; |
265 | } |
266 | |
267 | QList<QDoubleVector2D> QGeoSimplify::simplifyDouglasPeuckerZL(const QList<QDoubleVector2D> &points, |
268 | const double &leftBound, |
269 | int zoomLevel) |
270 | { |
271 | const int last = points.size() - 1; |
272 | QList<QDoubleVector2D> simplified { points.first() }; |
273 | simplifyDPStepZL(points, leftBound, first: 0, last, zoomLevel, simplified); |
274 | simplified.append(t: points.at(i: last)); |
275 | return simplified; |
276 | } |
277 | |
278 | QList<QGeoCoordinate> QGeoSimplify::geoSimplify(const QList<QGeoCoordinate> &points, |
279 | const double &leftBound, |
280 | double offsetTolerance) // also in meters |
281 | { |
282 | if (points.size() <= 2) |
283 | return points; |
284 | return simplifyDouglasPeucker(points, |
285 | leftBound, |
286 | offsetTolerance); |
287 | } |
288 | |
289 | QList<QDoubleVector2D> QGeoSimplify::geoSimplify(const QList<QDoubleVector2D> &points, |
290 | const double &leftBound, |
291 | double offsetTolerance) // also in meters |
292 | { |
293 | if (points.size() <= 2) |
294 | return points; |
295 | return simplifyDouglasPeucker(points, |
296 | leftBound, |
297 | offsetTolerance); |
298 | } |
299 | |
300 | QList<QDoubleVector2D> QGeoSimplify::geoSimplifyZL(const QList<QDoubleVector2D> &points, |
301 | const double &leftBound, |
302 | int zoomLevel) |
303 | { |
304 | if (points.size() <= 2) |
305 | return points; |
306 | return simplifyDouglasPeuckerZL(points, |
307 | leftBound, |
308 | zoomLevel); |
309 | } |
310 | |
311 | |
312 | QT_END_NAMESPACE |
313 | |
314 | |