diff options
Diffstat (limited to 'src/location/declarativemaps/qgeosimplify.cpp')
| -rw-r--r-- | src/location/declarativemaps/qgeosimplify.cpp | 313 |
1 files changed, 313 insertions, 0 deletions
diff --git a/src/location/declarativemaps/qgeosimplify.cpp b/src/location/declarativemaps/qgeosimplify.cpp new file mode 100644 index 00000000..9414a1cf --- /dev/null +++ b/src/location/declarativemaps/qgeosimplify.cpp @@ -0,0 +1,313 @@ +/**************************************************************************** +** +** Qt adaptation of geosimplify-js +** Copyright (C) 2017 Daniel Patterson +** See 3rdParty/geosimplify.js for the original license. +** +** Copyright (C) 2020 Paolo Angelelli <paolo.angelelli@gmail.com> +** Copyright (C) 2020 The Qt Company Ltd. +** Contact: http://www.qt.io/licensing/ +** +** This file is part of the QtLocation module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL3$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see http://www.qt.io/terms-conditions. For further +** information use the contact form at http://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPLv3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or later as published by the Free +** Software Foundation and appearing in the file LICENSE.GPL included in +** the packaging of this file. Please review the following information to +** ensure the GNU General Public License version 2.0 requirements will be +** met: http://www.gnu.org/licenses/gpl-2.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qgeosimplify_p.h" +#include <QtPositioning/private/qlocationutils_p.h> + +QT_BEGIN_NAMESPACE + +double QGeoSimplify::getDist(const QGeoCoordinate &p1, const QGeoCoordinate &p2) +{ + return p1.distanceTo(p2); +} + +QDoubleVector2D QGeoSimplify::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; + if (u > 0 && u < 1 + && (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); + } +} + +double QGeoSimplify::getDist(QDoubleVector2D a, QDoubleVector2D b, const 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)); +} + +void QGeoSimplify::simplifyDPStep(const QList<QDoubleVector2D> &points, + const double &leftBound, + int first, + int last, + double offsetTolerance, + QList<QDoubleVector2D> &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); + } +} + +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; +} + +static 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, + 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; + + 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) + simplifyDPStepZL(points, + leftBound, + first, + index, + zoomLevel, + simplified); + simplified.append(points.at(index)); + if (last - index > 1) + simplifyDPStepZL(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; +} + +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; +} + +QList<QGeoCoordinate> QGeoSimplify::geoSimplify(const QList<QGeoCoordinate> &points, + const double &leftBound, + double offsetTolerance) // also in meters +{ + 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); +} + +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 + |