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
45QT_BEGIN_NAMESPACE
46
47double QGeoSimplify::getDist(const QGeoCoordinate &p1, const QGeoCoordinate &p2)
48{
49 return p1.distanceTo(other: p2);
50}
51
52QDoubleVector2D 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
66QGeoCoordinate 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
88double 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
95double 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
101void 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
137double 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
147void 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
188static 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
196static 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
203void 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
247QList<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
257QList<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
267QList<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
278QList<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
289QList<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
300QList<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
312QT_END_NAMESPACE
313
314

source code of qtlocation/src/location/declarativemaps/qgeosimplify.cpp