Fix dragging items out of map bounds

In 5.9.0 map items are clipped against the visible region.
This implies that their geometry is also clipped against
the visible region.
This is problematic in ::geometryChanged, since the old
geometry is always clipped in this way.

This patch clips items against a "projectable" region
instead, that is the part of the map that is in front
of the camera.

Since this can produce very large vertices, mapbox
earcut 3rd party library is pulled in, to replace
qTriangulate that only supports coordinates up to
1<<21.

Task-number: QTBUG-61727
Change-Id: I7449e755a4848a2b2107c5de4e27821e3e887bfb
Reviewed-by: Paolo Angelelli <paolo.angelelli@qt.io>

5 files changed, 94 insertions, 23 deletions

diff --git a/src/location/declarativemaps/qdeclarativepolygonmapitem.cpp b/src/location/declarativemaps/qdeclarativepolygonmapitem.cpp
index daa1a9fc..3218f9f1 100644
--- a/src/location/declarativemaps/qdeclarativepolygonmapitem.cpp
+++ b/src/location/declarativemaps/qdeclarativepolygonmapitem.cpp
@@ -53,6 +53,8 @@
 
 /* poly2tri triangulator includes */
 #include <clip2tri.h>
+#include <earcut.hpp>
+#include <array>
 
 QT_BEGIN_NAMESPACE
 
@@ -185,7 +187,7 @@ void QGeoMapPolygonGeometry::updateSourcePoints(const QGeoMap &map,
 
     // 2)
     QList<QList<QDoubleVector2D> > clippedPaths;
-    const QList<QDoubleVector2D> &visibleRegion = map.geoProjection().visibleRegion();
+    const QList<QDoubleVector2D> &visibleRegion = map.geoProjection().projectableRegion();
     if (visibleRegion.size()) {
         c2t::clip2tri clipper;
         clipper.addSubjectPath(QClipperUtils::qListToPath(wrappedPath), true);
@@ -306,23 +308,42 @@ void QGeoMapPolygonGeometry::updateScreenPoints(const QGeoMap &map)
 
     screenOutline_ = ppi;
 
-    QTriangleSet ts = qTriangulate(ppi);
-    qreal *vx = ts.vertices.data();
-
-    screenIndices_.reserve(ts.indices.size());
-    screenVertices_.reserve(ts.vertices.size());
+    using Coord = double;
+    using N = uint32_t;
+    using Point = std::array<Coord, 2>;
+
+    std::vector<std::vector<Point>> polygon;
+    polygon.push_back(std::vector<Point>());
+    std::vector<Point> &poly = polygon.front();
+    // ... fill polygon structure with actual data
+
+    for (int i = 0; i < ppi.elementCount(); ++i) {
+        const QPainterPath::Element e = ppi.elementAt(i);
+        if (e.isMoveTo() || i == ppi.elementCount() - 1
+                || (qAbs(e.x - poly.front()[0]) < 0.1
+                    && qAbs(e.y - poly.front()[1]) < 0.1)) {
+            Point p = { e.x, e.y };
+            poly.push_back( p );
+        } else if (e.isLineTo()) {
+            Point p = { e.x, e.y };
+            poly.push_back( p );
+        } else {
+            qWarning("Unhandled element type in polygon painterpath");
+        }
+    }
 
-    if (ts.indices.type() == QVertexIndexVector::UnsignedInt) {
-        const quint32 *ix = reinterpret_cast<const quint32 *>(ts.indices.data());
-        for (int i = 0; i < (ts.indices.size()/3*3); ++i)
-            screenIndices_ << ix[i];
-    } else {
-        const quint16 *ix = reinterpret_cast<const quint16 *>(ts.indices.data());
-        for (int i = 0; i < (ts.indices.size()/3*3); ++i)
-            screenIndices_ << ix[i];
+    if (poly.size() > 2) {
+        // Run tessellation
+        // Returns array of indices that refer to the vertices of the input polygon.
+        // Three subsequent indices form a triangle.
+        screenVertices_.clear();
+        screenIndices_.clear();
+        for (const auto &p : poly)
+            screenVertices_ << QPointF(p[0], p[1]);
+        std::vector<N> indices = mapbox::earcut<N>(polygon);
+        for (const auto &i: indices)
+            screenIndices_ << quint32(i);
     }
-    for (int i = 0; i < (ts.vertices.size()/2*2); i += 2)
-        screenVertices_ << QPointF(vx[i], vx[i + 1]);
 
     screenBounds_ = ppi.boundingRect();
 }
diff --git a/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp b/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp
index aedb9811..26f030b0 100644
--- a/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp
+++ b/src/location/declarativemaps/qdeclarativepolylinemapitem.cpp
@@ -226,7 +226,7 @@ QList<QList<QDoubleVector2D> > QGeoMapPolylineGeometry::clipPath(const QGeoMap &
 
     // 2)
     QList<QList<QDoubleVector2D> > clippedPaths;
-    const QList<QDoubleVector2D> &visibleRegion = map.geoProjection().visibleRegion();
+    const QList<QDoubleVector2D> &visibleRegion = map.geoProjection().projectableRegion();
     if (visibleRegion.size()) {
         c2t::clip2tri clipper;
         clipper.addSubjectPath(QClipperUtils::qListToPath(wrappedPath), false);
diff --git a/src/location/location.pro b/src/location/location.pro
index 5dc89a63..a951ebd6 100644
--- a/src/location/location.pro
+++ b/src/location/location.pro
@@ -10,6 +10,7 @@ CONFIG += simd optimize_full
 # 3rdparty headers produce warnings with MSVC
 msvc: CONFIG -= warning_clean
 
+INCLUDEPATH += ../3rdparty/earcut
 INCLUDEPATH += ../3rdparty/poly2tri
 INCLUDEPATH += ../3rdparty/clipper
 INCLUDEPATH += ../3rdparty/clip2tri
diff --git a/src/location/maps/qgeoprojection.cpp b/src/location/maps/qgeoprojection.cpp
index 07747a31..609fb934 100644
--- a/src/location/maps/qgeoprojection.cpp
+++ b/src/location/maps/qgeoprojection.cpp
@@ -317,6 +317,13 @@ QList<QDoubleVector2D> QGeoProjectionWebMercator::visibleRegion() const
     return m_visibleRegion;
 }
 
+QList<QDoubleVector2D> QGeoProjectionWebMercator::projectableRegion() const
+{
+    if (m_visibleRegionDirty)
+        const_cast<QGeoProjectionWebMercator *>(this)->updateVisibleRegion();
+    return m_projectableRegion;
+}
+
 QDoubleVector2D QGeoProjectionWebMercator::viewportToWrappedMapProjection(const QDoubleVector2D &itemPosition) const
 {
     double s;
@@ -350,6 +357,8 @@ void QGeoProjectionWebMercator::setupCamera()
     int intZoomLevel = static_cast<int>(std::floor(m_cameraData.zoomLevel()));
     m_sideLength = (1 << intZoomLevel) * defaultTileSize;
     m_center = m_centerMercator * m_sideLength;
+    //aperture(90 / 2) = 1
+    m_aperture = tan(QLocationUtils::radians(m_cameraData.fieldOfView()) * 0.5);
 
     double f = m_viewportHeight;
     double z = std::pow(2.0, m_cameraData.zoomLevel() - intZoomLevel) * defaultTileSize;
@@ -358,15 +367,13 @@ void QGeoProjectionWebMercator::setupCamera()
     double z_mercator = std::pow(2.0, m_cameraData.zoomLevel()) * defaultTileSize;
     double altitude_mercator = f / (2.0 * z_mercator);
 
-    //aperture(90 / 2) = 1
-    m_aperture = tan(QLocationUtils::radians(m_cameraData.fieldOfView()) * 0.5);
     // calculate eye
     m_eye = m_center;
     m_eye.setZ(altitude * defaultTileSize / m_aperture);
 
     // And in mercator space
     m_eyeMercator = m_centerMercator;
-    m_eyeMercator.setZ(altitude_mercator);
+    m_eyeMercator.setZ(altitude_mercator  / m_aperture);
 
     m_view = m_eye - m_center;
     QDoubleVector3D side = QDoubleVector3D::normal(m_view, QDoubleVector3D(0.0, 1.0, 0.0));
@@ -402,7 +409,7 @@ void QGeoProjectionWebMercator::setupCamera()
         m_eyeMercator = mTiltMercator * m_viewMercator + m_centerMercator;
     }
 
-    m_view = m_eye - m_center;
+    m_view = m_eye - m_center; // ToDo: this should be inverted (center - eye), and the rest should follow
     m_viewNormalized = m_view.normalized();
     m_up = QDoubleVector3D::normal(m_view, m_side);
 
@@ -455,7 +462,7 @@ void QGeoProjectionWebMercator::setupCamera()
     m_transformation.scale(m_sideLength, m_sideLength, 1.0);
 
     m_centerNearPlane = m_eye + m_viewNormalized;
-    m_centerNearPlaneMercator = m_eyeMercator + m_viewNormalized * m_nearPlaneMercator;
+    m_centerNearPlaneMercator = m_eyeMercator - m_viewNormalized * m_nearPlaneMercator;
 
     // The method does not support tilting angles >= 90.0 or < 0.
 
@@ -505,6 +512,46 @@ void QGeoProjectionWebMercator::updateVisibleRegion()
     m_visibleRegion.clear();
     if (res.size())
         m_visibleRegion = QClipperUtils::pathToQList(res[0]); // Intersection between two convex quadrilaterals should always be a single polygon
+
+    m_projectableRegion.clear();
+    if (m_cameraData.tilt() == 0) {
+        m_projectableRegion = mapRect;
+    } else {
+        QGeoProjectionWebMercator::Plane nearPlane(m_centerNearPlaneMercator, m_viewNormalized);
+        Line2D nearPlaneXYIntersection = nearPlane.planeXYIntersection();
+        double squareHalfSide = qMax(5.0, nearPlaneXYIntersection.m_point.length());
+        QDoubleVector2D viewDirectionProjected = -m_viewNormalized.toVector2D().normalized();
+
+
+        QDoubleVector2D tl = nearPlaneXYIntersection.m_point
+                            - squareHalfSide * nearPlaneXYIntersection.m_direction
+                            + 2 * squareHalfSide * viewDirectionProjected;
+        QDoubleVector2D tr = nearPlaneXYIntersection.m_point
+                            + squareHalfSide * nearPlaneXYIntersection.m_direction
+                            + 2 * squareHalfSide * viewDirectionProjected;
+        QDoubleVector2D bl = nearPlaneXYIntersection.m_point
+                            - squareHalfSide * nearPlaneXYIntersection.m_direction;
+        QDoubleVector2D br = nearPlaneXYIntersection.m_point
+                            + squareHalfSide * nearPlaneXYIntersection.m_direction;
+
+        QList<QDoubleVector2D> projectableRect;
+        projectableRect.push_back(bl);
+        projectableRect.push_back(br);
+        projectableRect.push_back(tr);
+        projectableRect.push_back(tl);
+
+
+        c2t::clip2tri clipperProjectable;
+        clipperProjectable.clearClipper();
+        clipperProjectable.addSubjectPath(QClipperUtils::qListToPath(mapRect), true);
+        clipperProjectable.addClipPolygon(QClipperUtils::qListToPath(projectableRect));
+
+        Paths resProjectable = clipperProjectable.execute(c2t::clip2tri::Intersection);
+        if (resProjectable.size())
+            m_projectableRegion = QClipperUtils::pathToQList(resProjectable[0]); // Intersection between two convex quadrilaterals should always be a single polygon
+        else
+            m_projectableRegion = viewportRect;
+    }
 }
 
 /*
diff --git a/src/location/maps/qgeoprojection_p.h b/src/location/maps/qgeoprojection_p.h
index 7d306eea..76e11af0 100644
--- a/src/location/maps/qgeoprojection_p.h
+++ b/src/location/maps/qgeoprojection_p.h
@@ -73,6 +73,7 @@ public:
 
     virtual bool isProjectable(const QDoubleVector2D &wrappedProjection) const = 0;
     virtual QList<QDoubleVector2D> visibleRegion() const = 0;
+    virtual QList<QDoubleVector2D> projectableRegion() const = 0;
 
     // Conversion methods for QGeoCoordinate <-> screen.
     // This currently assumes that the "MapProjection" space is [0, 1][0, 1] for every type of possibly supported map projection
@@ -126,7 +127,7 @@ public:
 
     bool isProjectable(const QDoubleVector2D &wrappedProjection) const Q_DECL_OVERRIDE;
     QList<QDoubleVector2D> visibleRegion() const Q_DECL_OVERRIDE;
-
+    QList<QDoubleVector2D> projectableRegion() const Q_DECL_OVERRIDE;
     inline QDoubleVector2D viewportToWrappedMapProjection(const QDoubleVector2D &itemPosition) const;
     inline QDoubleVector2D viewportToWrappedMapProjection(const QDoubleVector2D &itemPosition, double &s) const;
 private:
@@ -202,6 +203,7 @@ private:
     Line2D           m_nearPlaneMapIntersection;
 
     QList<QDoubleVector2D> m_visibleRegion;
+    QList<QDoubleVector2D> m_projectableRegion;
     bool             m_visibleRegionDirty;
 
     Q_DISABLE_COPY(QGeoProjectionWebMercator)