summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/location/declarativemaps/qgeosimplify.cpp273
-rw-r--r--src/location/declarativemaps/qgeosimplify_p.h97
2 files changed, 73 insertions, 297 deletions
diff --git a/src/location/declarativemaps/qgeosimplify.cpp b/src/location/declarativemaps/qgeosimplify.cpp
index e7955fd8..ad5a3c5d 100644
--- a/src/location/declarativemaps/qgeosimplify.cpp
+++ b/src/location/declarativemaps/qgeosimplify.cpp
@@ -5,7 +5,7 @@
** See 3rdParty/geosimplify.js for the original license.
**
** Copyright (C) 2020 Paolo Angelelli <paolo.angelelli@gmail.com>
-** Copyright (C) 2020 The Qt Company Ltd.
+** Copyright (C) 2022 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtLocation module of the Qt Toolkit.
@@ -44,182 +44,84 @@
#include "qgeosimplify_p.h"
#include <QtPositioning/private/qlocationutils_p.h>
+#include <QtPositioning/private/qdoublevector2d_p.h>
+#include <QtPositioning/private/qwebmercator_p.h>
QT_BEGIN_NAMESPACE
-double QGeoSimplify::getDist(const QGeoCoordinate &p1, const QGeoCoordinate &p2)
-{
- return p1.distanceTo(p2);
-}
+namespace {
-QDoubleVector2D QGeoSimplify::closestPoint(const QDoubleVector2D &p, const QDoubleVector2D &a, const QDoubleVector2D &b)
+// p, a and b are intended as "unwrapped" around the left bound
+inline QDoubleVector2D closestPoint(const QDoubleVector2D &p,
+ const QDoubleVector2D &a,
+ const QDoubleVector2D &b)
{
if (a == b)
return a;
- const double u = ((p.x() - a.x()) * (b.x() - a.x()) + (p.y() - a.y()) * (b.y() - a.y()) ) / (b - a).lengthSquared();
- const QDoubleVector2D intersection(a.x() + u * (b.x() - a.x()) , a.y() + u * (b.y() - a.y()) );
- QDoubleVector2D candidate = ( (p-a).length() < (p-b).length() ) ? a : b;
+ const double u = ((p.x() - a.x()) * (b.x() - a.x()) + (p.y() - a.y()) * (b.y() - a.y()))
+ / (b - a).lengthSquared();
+ const QDoubleVector2D intersection(a.x() + u * (b.x() - a.x()) , a.y() + u * (b.y() - a.y()));
+ QDoubleVector2D candidate = ((p - a).length() < (p - b).length()) ? a : b;
if (u > 0 && u < 1
- && (p-intersection).length() < (p-candidate).length() ) // And it falls in the segment
+ && (p - intersection).length() < (p - candidate).length()) { // And it falls in the segment
candidate = intersection;
- return candidate;
-}
-
-QGeoCoordinate QGeoSimplify::closestPoint(const QGeoCoordinate &pc, const QGeoCoordinate &ac, const QGeoCoordinate &bc, const double &leftBound)
-{
- QDoubleVector2D p = QWebMercator::coordToMercator(pc);
- if (p.x() < leftBound)
- p.setX(p.x() + leftBound); // unwrap X
-
- QDoubleVector2D a = QWebMercator::coordToMercator(ac);
- if (a.x() < leftBound)
- a.setX(a.x() + leftBound); // unwrap X
-
- QDoubleVector2D b = QWebMercator::coordToMercator(bc);
- if (b.x() < leftBound)
- b.setX(b.x() + leftBound); // unwrap X
-
- QDoubleVector2D intersection = closestPoint(p, a, b);
- if (intersection.x() > 1.0)
- intersection.setX(intersection.x() - leftBound); // wrap X
-
- const QGeoCoordinate closest = QWebMercator::mercatorToCoord(intersection);
- return closest;
-}
-
-double QGeoSimplify::getSegDist(const QGeoCoordinate &pc, const QGeoCoordinate &ac, const QGeoCoordinate &bc, const double &leftBound)
-{
- const QGeoCoordinate closest = closestPoint(pc, ac, bc, leftBound);
- const double distanceMeters = pc.distanceTo(closest);
- return distanceMeters;
-}
-
-double QGeoSimplify::getSegDist(const QDoubleVector2D &p, const QDoubleVector2D &a, const QDoubleVector2D &b, const double &leftBound)
-{
- QDoubleVector2D intersection = closestPoint(p, a, b);
- return getDist(intersection, p, leftBound);
-}
-
-void QGeoSimplify::simplifyDPStep(const QList<QGeoCoordinate> &points, const double &leftBound, int first, int last, double offsetTolerance, QList<QGeoCoordinate> &simplified)
-{
- double maxDistanceFound = offsetTolerance;
- int index = 0;
-
- for (int i = first + 1; i < last; i++) {
- const double distance = getSegDist(points.at(i),
- points.at(first),
- points.at(last),
- leftBound);
-
- if (distance > maxDistanceFound) {
- index = i;
- maxDistanceFound = distance;
- }
- }
-
- if (index > 0) {
- if (index - first > 1)
- simplifyDPStep(points,
- leftBound,
- first,
- index,
- offsetTolerance,
- simplified);
- simplified.append(points.at(index));
- if (last - index > 1)
- simplifyDPStep(points,
- leftBound,
- index,
- last,
- offsetTolerance,
- simplified);
}
+ return candidate;
}
-double QGeoSimplify::getDist(QDoubleVector2D a, QDoubleVector2D b, const double &leftBound)
+inline double getDist(QDoubleVector2D a, QDoubleVector2D b, double leftBound)
{
if (a.x() > 1.0)
a.setX(a.x() - leftBound); // wrap X
if (b.x() > 1.0)
b.setX(b.x() - leftBound); // wrap X
- return QWebMercator::mercatorToCoord(a).distanceTo(
- QWebMercator::mercatorToCoord(b));
+ return QWebMercator::mercatorToCoord(a).distanceTo(QWebMercator::mercatorToCoord(b));
}
-void QGeoSimplify::simplifyDPStep(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- int first,
- int last,
- double offsetTolerance,
- QList<QDoubleVector2D> &simplified)
+// doublevectors Intended as wrapped
+inline double getSegDist(const QDoubleVector2D &p,
+ const QDoubleVector2D &a,
+ const QDoubleVector2D &b,
+ double leftBound)
{
- double maxDistanceFound = offsetTolerance;
- int index = 0;
-
- for (int i = first + 1; i < last; i++) {
- const double distance = getSegDist(points.at(i),
- points.at(first),
- points.at(last),
- leftBound);
-
- if (distance > maxDistanceFound) {
- index = i;
- maxDistanceFound = distance;
- }
- }
-
- if (index > 0) {
- if (index - first > 1)
- simplifyDPStep(points,
- leftBound,
- first,
- index,
- offsetTolerance,
- simplified);
- simplified.append(points.at(index));
- if (last - index > 1)
- simplifyDPStep(points,
- leftBound,
- index,
- last,
- offsetTolerance,
- simplified);
- }
-}
-
-static double pixelDistanceAtZoomAndLatitude(int zoom, double latitude)
-{
- const double den = double((1 << (zoom + 8)));
- const double pixelDist = (QLocationUtils::earthMeanCircumference() *
- std::cos(QLocationUtils::radians(latitude))) / den;
- return pixelDist;
+ const QDoubleVector2D intersection = closestPoint(p, a, b);
+ return getDist(intersection, p, leftBound);
}
-static QGeoCoordinate unwrappedToGeo(QDoubleVector2D p, double leftBound)
+inline QGeoCoordinate unwrappedToGeo(QDoubleVector2D p, double leftBound)
{
if (p.x() > 1.0)
p.setX(p.x() - leftBound);
return QWebMercator::mercatorToCoord(p);
}
-void QGeoSimplify::simplifyDPStepZL(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- int first,
- int last,
- int zoomLevel,
+double pixelDistanceAtZoomAndLatitude(int zoom, double latitude)
+{
+ const double den = double((1 << (zoom + 8)));
+ const double pixelDist = (QLocationUtils::earthMeanCircumference()
+ * std::cos(QLocationUtils::radians(latitude)))
+ / den;
+ return pixelDist;
+}
+
+// simplification using Ramer-Douglas-Peucker algorithm
+void simplifyDouglasPeuckerStepZL(const QList<QDoubleVector2D> &points, double leftBound,
+ qsizetype first, qsizetype last, int zoomLevel,
QList<QDoubleVector2D> &simplified)
{
const QGeoCoordinate firstC = unwrappedToGeo(points.at(first), leftBound);
const QGeoCoordinate lastC = unwrappedToGeo(points.at(last), leftBound);
double maxDistanceFound = (pixelDistanceAtZoomAndLatitude(zoomLevel, firstC.latitude())
- + pixelDistanceAtZoomAndLatitude(zoomLevel, lastC.latitude())) * 0.5;
- int index = 0;
+ + pixelDistanceAtZoomAndLatitude(zoomLevel, lastC.latitude())) * 0.5;
+ qsizetype index = -1;
- for (int i = first + 1; i < last; i++) {
+ const auto &firstPoint = points.at(first);
+ const auto &lastPoint = points.at(last);
+ for (qsizetype i = first + 1; i < last; i++) {
const double distance = getSegDist(points.at(i),
- points.at(first),
- points.at(last),
+ firstPoint,
+ lastPoint,
leftBound);
if (distance > maxDistanceFound) {
@@ -229,88 +131,37 @@ void QGeoSimplify::simplifyDPStepZL(const QList<QDoubleVector2D> &points,
}
if (index > 0) {
- if (index - first > 1)
- simplifyDPStepZL(points,
- leftBound,
- first,
- index,
- zoomLevel,
- simplified);
+ if (index - first > 1) {
+ simplifyDouglasPeuckerStepZL(points, leftBound,
+ first, index, zoomLevel,
+ simplified);
+ }
simplified.append(points.at(index));
- if (last - index > 1)
- simplifyDPStepZL(points,
- leftBound,
- index,
- last,
- zoomLevel,
- simplified);
+ if (last - index > 1) {
+ simplifyDouglasPeuckerStepZL(points, leftBound,
+ index, last, zoomLevel,
+ simplified);
+ }
}
}
-QList<QGeoCoordinate> QGeoSimplify::simplifyDouglasPeucker(const QList<QGeoCoordinate> &points,
- const double &leftBound,
- double offsetTolerance) {
- const int last = points.size() - 1;
- QList<QGeoCoordinate> simplified { points.first() };
- simplifyDPStep(points, leftBound, 0, last, offsetTolerance, simplified);
- simplified.append(points.at(last));
- return simplified;
-}
-
-QList<QDoubleVector2D> QGeoSimplify::simplifyDouglasPeucker(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- double offsetTolerance) {
- const int last = points.size() - 1;
- QList<QDoubleVector2D> simplified { points.first() };
- simplifyDPStep(points, leftBound, 0, last, offsetTolerance, simplified);
- simplified.append(points.at(last));
- return simplified;
-}
+} // anonymous namespace
-QList<QDoubleVector2D> QGeoSimplify::simplifyDouglasPeuckerZL(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- int zoomLevel)
-{
- const int last = points.size() - 1;
- QList<QDoubleVector2D> simplified { points.first() };
- simplifyDPStepZL(points, leftBound, 0, last, zoomLevel, simplified);
- simplified.append(points.at(last));
- return simplified;
-}
+namespace QGeoSimplify {
-QList<QGeoCoordinate> QGeoSimplify::geoSimplify(const QList<QGeoCoordinate> &points,
- const double &leftBound,
- double offsetTolerance) // also in meters
+QList<QDoubleVector2D> geoSimplifyZL(const QList<QDoubleVector2D> &points,
+ double leftBound, int zoomLevel)
{
if (points.size() <= 2)
return points;
- return simplifyDouglasPeucker(points,
- leftBound,
- offsetTolerance);
-}
-QList<QDoubleVector2D> QGeoSimplify::geoSimplify(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- double offsetTolerance) // also in meters
-{
- if (points.size() <= 2)
- return points;
- return simplifyDouglasPeucker(points,
- leftBound,
- offsetTolerance);
+ const qsizetype last = points.size() - 1;
+ QList<QDoubleVector2D> simplified { points.first() };
+ simplifyDouglasPeuckerStepZL(points, leftBound, 0, last, zoomLevel, simplified);
+ simplified.append(points.at(last));
+ return simplified;
}
-QList<QDoubleVector2D> QGeoSimplify::geoSimplifyZL(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- int zoomLevel)
-{
- if (points.size() <= 2)
- return points;
- return simplifyDouglasPeuckerZL(points,
- leftBound,
- zoomLevel);
}
-
QT_END_NAMESPACE
-
diff --git a/src/location/declarativemaps/qgeosimplify_p.h b/src/location/declarativemaps/qgeosimplify_p.h
index 567845de..1f5c9783 100644
--- a/src/location/declarativemaps/qgeosimplify_p.h
+++ b/src/location/declarativemaps/qgeosimplify_p.h
@@ -3,7 +3,7 @@
** Qt adaptation of geosimplify.js, https://github.com/mapbox/geosimplify-js, (c) 2017, Mapbox
**
** Copyright (C) 2020 Paolo Angelelli <paolo.angelelli@gmail.com>
-** Copyright (C) 2020 The Qt Company Ltd.
+** Copyright (C) 2022 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtLocation module of the Qt Toolkit.
@@ -54,96 +54,21 @@
// We mean it.
//
-#include <QtPositioning/QGeoCoordinate>
-#include <QtPositioning/private/qdoublevector2d_p.h>
-#include <QtPositioning/private/qwebmercator_p.h>
+#include <QtCore/QList>
QT_BEGIN_NAMESPACE
-class QGeoSimplify {
-protected:
- // Distance between two points in metres
- static double getDist(const QGeoCoordinate &p1, const QGeoCoordinate &p2);
+class QDoubleVector2D;
- // p, a and b are intended as "unwrapped" around the left bound
- static QDoubleVector2D closestPoint( const QDoubleVector2D &p,
- const QDoubleVector2D &a,
- const QDoubleVector2D &b);
-
- static QGeoCoordinate closestPoint( const QGeoCoordinate &pc,
- const QGeoCoordinate &ac,
- const QGeoCoordinate &bc,
- const double &leftBound);
-
- // Distance from a point to a segment (line between two points) in metres
- static double getSegDist(const QGeoCoordinate &pc,
- const QGeoCoordinate &ac,
- const QGeoCoordinate &bc,
- const double &leftBound);
-
- // doublevectors Intended as wrapped
- static double getSegDist(const QDoubleVector2D &p,
- const QDoubleVector2D &a,
- const QDoubleVector2D &b,
- const double &leftBound);
-
- static void simplifyDPStep(const QList<QGeoCoordinate> &points,
- const double &leftBound,
- int first,
- int last,
- double offsetTolerance,
- QList<QGeoCoordinate> &simplified);
-
- static double getDist(QDoubleVector2D a,
- QDoubleVector2D b,
- const double &leftBound);
-
- static void simplifyDPStep(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- int first,
- int last,
- double offsetTolerance,
- QList<QDoubleVector2D> &simplified);
-
- static void simplifyDPStepZL(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- int first,
- int last,
- int zoomLevel,
- QList<QDoubleVector2D> &simplified);
-
- // simplification using Ramer-Douglas-Peucker algorithm
- static QList<QGeoCoordinate> simplifyDouglasPeucker(const QList<QGeoCoordinate> &points,
- const double &leftBound,
- double offsetTolerance);
-
- static QList<QDoubleVector2D> simplifyDouglasPeucker(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- double offsetTolerance);
-
- static QList<QDoubleVector2D> simplifyDouglasPeuckerZL(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- int zoomLevel);
-
-public:
- /*
- offsetTolerance - how far outside the straight line a point
- needs to be for it to be "kept"
- */
- static QList<QGeoCoordinate> geoSimplify(const QList<QGeoCoordinate> &points,
- const double &leftBound,
- double offsetTolerance); // in meters
-
- static QList<QDoubleVector2D> geoSimplify(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- double offsetTolerance); // in meters
-
- // This overload tries to be adaptive in the offsetTolerance across latitudes,
+namespace QGeoSimplify
+{
+ // offsetTolerance - how far outside the straight line a point
+ // needs to be for it to be "kept"
+ // This function tries to be adaptive in the offsetTolerance across latitudes,
// and return a simplification adequate for the given zoomLevel.
- static QList<QDoubleVector2D> geoSimplifyZL(const QList<QDoubleVector2D> &points,
- const double &leftBound,
- int zoomLevel); // in meters
-};
+ QList<QDoubleVector2D> geoSimplifyZL(const QList<QDoubleVector2D> &points,
+ double leftBound, int zoomLevel); // in meters
+}
QT_END_NAMESPACE