Add clipping for rotated/tilted Map Items

This patch adds proper rotation/tilting support to Map Items.
To do so, clipping is now performed in wrapped mercator space
instead of screen space.
This prevents projection of geo coordinates that ended behind
the camera, and that would be projected incorrectly by the
projection transformation.

This patch therefore does not use the screen clipping code
any longer (clipPathToRect), since the geometry has already
been clipped.
The downside is that updateSourcePoints is now necessary for
any viewport change.

This would be necessary anyway in presence of tilt or rotation.

NB: Handling of MapQuickItems with zoomLevel set is still TODO.

Future work:
1) Optimize updateSourcePoints by pre-computing the mercator
projection of the geometry, and let updateSourcePoints do only
the wrapping/clipping/projection-to-screen operations.

2) Remove updateScreenPoints altogether

Change-Id: Ie0d3dbef68d48ac97a596d40240d0ac126c0efaf
Reviewed-by: Alex Blasche <alexander.blasche@qt.io>
Reviewed-by: Paolo Angelelli <paolo.angelelli@qt.io>
Reviewed-by: Laszlo Agocs <laszlo.agocs@qt.io>
Reviewed-by: Eskil Abrahamsen Blomfeldt <eskil.abrahamsen-blomfeldt@qt.io>

7 files changed, 262 insertions, 16 deletions

diff --git a/src/positioning/positioning.pro b/src/positioning/positioning.pro
index c4c9cc6c..0df56a71 100644
--- a/src/positioning/positioning.pro
+++ b/src/positioning/positioning.pro
@@ -1,6 +1,10 @@
 TARGET = QtPositioning
 QT = core-private
 
+#INCLUDEPATH += ../3rdparty/poly2tri
+INCLUDEPATH += ../3rdparty/clipper
+INCLUDEPATH += ../3rdparty/clip2tri
+
 QMAKE_DOCS = $$PWD/doc/qtpositioning.qdocconf
 OTHER_FILES += doc/src/*.qdoc   # show .qdoc files in Qt Creator
 
@@ -53,7 +57,8 @@ PRIVATE_HEADERS += \
                     qpositioningglobal_p.h \
                     qlocationdata_simulator_p.h \
                     qdoublematrix4x4_p.h \
-                    qgeopath_p.h
+                    qgeopath_p.h \
+                    qclipperutils_p.h
 
 SOURCES += \
             qgeoaddress.cpp \
@@ -78,9 +83,12 @@ SOURCES += \
             qgeopath.cpp \
             qlocationdata_simulator.cpp \
             qwebmercator.cpp \
-            qdoublematrix4x4.cpp
+            qdoublematrix4x4.cpp \
+            qclipperutils.cpp
 
 HEADERS += $$PUBLIC_HEADERS $$PRIVATE_HEADERS
 
 
 load(qt_module)
+
+LIBS_PRIVATE += -L$$MODULE_BASE_OUTDIR/lib -lclip2tri$$qtPlatformTargetSuffix()
diff --git a/src/positioning/qclipperutils.cpp b/src/positioning/qclipperutils.cpp
new file mode 100644
index 00000000..08e65712
--- /dev/null
+++ b/src/positioning/qclipperutils.cpp
@@ -0,0 +1,100 @@
+/****************************************************************************
+**
+** Copyright (C) 2016 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtPositioning module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** 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 https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://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.LGPL3 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-3.0.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 (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qclipperutils_p.h"
+
+QT_BEGIN_NAMESPACE
+
+static const double kClipperScaleFactor = 281474976710656.0;  // 48 bits of precision
+static const double kClipperScaleFactorInv = 1.0 / kClipperScaleFactor;
+
+double QClipperUtils::clipperScaleFactor()
+{
+    return kClipperScaleFactor;
+}
+
+QDoubleVector2D QClipperUtils::toVector2D(const IntPoint &p)
+{
+    return QDoubleVector2D(double(p.X) * kClipperScaleFactorInv, double(p.Y) * kClipperScaleFactorInv);
+}
+
+IntPoint QClipperUtils::toIntPoint(const QDoubleVector2D &p)
+{
+    return IntPoint(cInt(p.x() * kClipperScaleFactor), cInt(p.y() * kClipperScaleFactor));
+}
+
+QList<QDoubleVector2D> QClipperUtils::pathToQList(const Path &path)
+{
+    QList<QDoubleVector2D> res;
+    res.reserve(path.size());
+    for (const IntPoint &ip: path)
+        res.append(toVector2D(ip));
+    return res;
+}
+
+QList<QList<QDoubleVector2D> > QClipperUtils::pathsToQList(const Paths &paths)
+{
+    QList<QList<QDoubleVector2D> > res;
+    res.reserve(paths.size());
+    for (const Path &p: paths) {
+        res.append(pathToQList(p));
+    }
+    return res;
+}
+
+Path QClipperUtils::qListToPath(const QList<QDoubleVector2D> &list)
+{
+    Path res;
+    res.reserve(list.size());
+    for (const QDoubleVector2D &p: list)
+        res.push_back(toIntPoint(p));
+    return res;
+}
+
+Paths QClipperUtils::qListToPaths(const QList<QList<QDoubleVector2D> > &lists)
+{
+    Paths res;
+    res.reserve(lists.size());
+    for (const QList<QDoubleVector2D> &l: lists) {
+        res.push_back(qListToPath(l));
+    }
+    return res;
+}
+
+QT_END_NAMESPACE
diff --git a/src/positioning/qclipperutils_p.h b/src/positioning/qclipperutils_p.h
new file mode 100644
index 00000000..f05d9838
--- /dev/null
+++ b/src/positioning/qclipperutils_p.h
@@ -0,0 +1,86 @@
+/****************************************************************************
+**
+** Copyright (C) 2016 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtPositioning module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** 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 https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://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.LGPL3 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-3.0.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 (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+#ifndef QCLIPPERUTILS_P_H
+#define QCLIPPERUTILS_P_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists purely as an
+// implementation detail.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+/*
+ * This file is intended to be include only in source files of
+ * QtPositioning/QtLocation. It is in QtPositioning to enable manipulation
+ * of geo polygons
+ */
+
+#include <QtPositioning/private/qpositioningglobal_p.h>
+#include <QtCore/QtGlobal>
+#include <QtCore/QList>
+#include <cmath>
+/* clip2tri triangulator includes */
+#include <clip2tri.h>
+#include <QtPositioning/private/qdoublevector2d_p.h>
+
+QT_BEGIN_NAMESPACE
+
+class Q_POSITIONING_PRIVATE_EXPORT QClipperUtils
+{
+public:
+    static double clipperScaleFactor();
+
+    static QDoubleVector2D  toVector2D(const IntPoint &p);
+    static IntPoint         toIntPoint(const QDoubleVector2D &p);
+
+    static QList<QDoubleVector2D> pathToQList(const Path &path);
+    static QList<QList<QDoubleVector2D> > pathsToQList(const Paths &paths);
+
+    static Path  qListToPath(const QList<QDoubleVector2D> &list);
+    static Paths qListToPaths(const QList<QList<QDoubleVector2D> > &lists);
+};
+
+QT_END_NAMESPACE
+
+#endif // QCLIPPERUTILS_P_H
diff --git a/src/positioning/qgeocircle.cpp b/src/positioning/qgeocircle.cpp
index 4b4370bf..6fccb8af 100644
--- a/src/positioning/qgeocircle.cpp
+++ b/src/positioning/qgeocircle.cpp
@@ -316,11 +316,11 @@ void QGeoCirclePrivate::updateBoundingBox()
             ));
 
         QGeoCoordinate topLeft;
-        topLeft.setLatitude(m_center.latitude() + lat_delta_in_deg);
-        topLeft.setLongitude(m_center.longitude() - lon_delta_in_deg);
+        topLeft.setLatitude(QLocationUtils::clipLat(m_center.latitude() + lat_delta_in_deg));
+        topLeft.setLongitude(QLocationUtils::wrapLong(m_center.longitude() - lon_delta_in_deg));
         QGeoCoordinate bottomRight;
-        bottomRight.setLatitude(m_center.latitude() - lat_delta_in_deg);
-        bottomRight.setLongitude(m_center.longitude() + lon_delta_in_deg);
+        bottomRight.setLatitude(QLocationUtils::clipLat(m_center.latitude() - lat_delta_in_deg));
+        bottomRight.setLongitude(QLocationUtils::wrapLong(m_center.longitude() + lon_delta_in_deg));
 
         m_bbox = QGeoRectangle(topLeft, bottomRight);
     }
diff --git a/src/positioning/qlocationutils_p.h b/src/positioning/qlocationutils_p.h
index 704a57f8..c73a2c3b 100644
--- a/src/positioning/qlocationutils_p.h
+++ b/src/positioning/qlocationutils_p.h
@@ -52,12 +52,16 @@
 
 #include <QtCore/QtGlobal>
 #include <math.h>
+#include <QtPositioning/QGeoCoordinate>
 
 static const double M_PID     = 3.14159265358979323846264338327950288; // to get more precision than float
 static const double M_1_180D  = 0.0055555555555555555555555555555555555555556;
 static const double M_1_PID   = 1.0 / M_PID;
 static const double M_PI_180D = M_PID / 180.0; //0.0174532925199432954743716805978692718781530857086181640625;
 static const double M_180_PID = 180.0 / M_PID; // 57.29577951308232286464772187173366546630859375
+static const double offsetEpsilon = 0.0000000000001;
+static const double leftOffset = -180.0 + offsetEpsilon;
+static const double rightOffset = 180.0 - offsetEpsilon;
 
 QT_BEGIN_NAMESPACE
 class QTime;
@@ -87,25 +91,25 @@ public:
     };
 
     inline static bool isValidLat(double lat) {
-        return lat >= -90 && lat <= 90;
+        return lat >= -90.0 && lat <= 90.0;
     }
     inline static bool isValidLong(double lng) {
-        return lng >= -180 && lng <= 180;
+        return lng >= -180.0 && lng <= 180.0;
     }
 
     inline static double clipLat(double lat) {
-        if (lat > 90)
-            lat = 90;
-        else if (lat < -90)
-            lat = -90;
+        if (lat > 90.0)
+            lat = 90.0;
+        else if (lat < -90.0)
+            lat = -90.0;
         return lat;
     }
 
     inline static double wrapLong(double lng) {
-        if (lng > 180)
-            lng -= 360;
-        else if (lng < -180)
-            lng += 360;
+        if (lng > 180.0)
+            lng -= 360.0;
+        else if (lng < -180.0)
+            lng += 360.0;
         return lng;
     }
 
@@ -212,16 +216,39 @@ public:
     {
         return radians * M_180_PID;
     }
+
     inline static double earthMeanRadius()
     {
         return 6371007.2;
     }
 
+    inline static double earthMeanDiameter()
+    {
+        return earthMeanRadius() * 2.0 * M_PID;
+    }
+
     inline static double mercatorMaxLatitude()
     {
         return 85.05113;
     }
 
+    inline static QGeoCoordinate antipodalPoint(const QGeoCoordinate &p)
+    {
+        return QGeoCoordinate(-p.latitude(), wrapLong(p.longitude() + 180.0));
+    }
+
+    // Leftmost longitude before wrapping kicks in
+    inline static double mapLeftLongitude(double centerLongitude)
+    {
+        return wrapLong(centerLongitude + leftOffset);
+    }
+
+    // Rightmost longitude before wrapping kicks in
+    inline static double  mapRightLongitude(double centerLongitude)
+    {
+        return wrapLong(centerLongitude - leftOffset);
+    }
+
     /*
         Creates a QGeoPositionInfo from a GGA, GLL, RMC, VTG or ZDA sentence.
 
diff --git a/src/positioning/qwebmercator.cpp b/src/positioning/qwebmercator.cpp
index d22258a7..da35c7d7 100644
--- a/src/positioning/qwebmercator.cpp
+++ b/src/positioning/qwebmercator.cpp
@@ -101,6 +101,30 @@ QGeoCoordinate QWebMercator::mercatorToCoord(const QDoubleVector2D &mercator)
     return QGeoCoordinate(lat, lng, 0.0);
 }
 
+QGeoCoordinate QWebMercator::mercatorToCoordClamped(const QDoubleVector2D &mercator)
+{
+    double fx = mercator.x();
+    double fy = mercator.y();
+
+    if (fy < 0.0)
+        fy = 0.0;
+    else if (fy > 1.0)
+        fy = 1.0;
+
+    double lat = (180.0 / M_PI) * (2.0 * std::atan(std::exp(M_PI * (1.0 - 2.0 * fy))) - (M_PI / 2.0));
+
+    double lng;
+    if (fx >= 0) {
+        lng = realmod(fx, 1.0);
+    } else {
+        lng = realmod(1.0 - realmod(-1.0 * fx, 1.0), 1.0);
+    }
+
+    lng = lng * 360.0 - 180.0;
+
+    return QGeoCoordinate(lat, lng, 0.0);
+}
+
 QGeoCoordinate QWebMercator::coordinateInterpolation(const QGeoCoordinate &from, const QGeoCoordinate &to, qreal progress)
 {
     QDoubleVector2D s = QWebMercator::coordToMercator(from);
diff --git a/src/positioning/qwebmercator_p.h b/src/positioning/qwebmercator_p.h
index 8c324710..2b8e9564 100644
--- a/src/positioning/qwebmercator_p.h
+++ b/src/positioning/qwebmercator_p.h
@@ -65,6 +65,7 @@ class Q_POSITIONING_PRIVATE_EXPORT QWebMercator
 public:
     static QDoubleVector2D coordToMercator(const QGeoCoordinate &coord);
     static QGeoCoordinate mercatorToCoord(const QDoubleVector2D &mercator);
+    static QGeoCoordinate mercatorToCoordClamped(const QDoubleVector2D &mercator);
     static QGeoCoordinate coordinateInterpolation(const QGeoCoordinate &from, const QGeoCoordinate &to, qreal progress);
 
 private: