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>

3 files changed, 69 insertions, 66 deletions

diff --git a/src/3rdparty/clip2tri/clip2tri.cpp b/src/3rdparty/clip2tri/clip2tri.cpp
index 16b1b86b..2f502667 100644
--- a/src/3rdparty/clip2tri/clip2tri.cpp
+++ b/src/3rdparty/clip2tri/clip2tri.cpp
@@ -27,10 +27,12 @@
  */
 
 #include "clip2tri.h"
-#include "../poly2tri/poly2tri.h"
+#include <poly2tri.h>
 
 #include <cstdio>
 
+static const double clipperScaleFactor = 1073741822.0;
+static const double clipperScaleFactorInv = 1.0 / 1073741822.0;
 
 using namespace p2t;
 
@@ -41,9 +43,6 @@ namespace c2t
 static const F32 CLIPPER_SCALE_FACT = 1000.0f;
 static const F32 CLIPPER_SCALE_FACT_INVERSE = 0.001f;
 
-static const F64 CLIPPER_SCALE_FACT_D = double(1<<31);
-static const F64 CLIPPER_SCALE_FACT_INVERSE_D = 1.0 / double(1<<31);
-
 /////////////////////////////////
 
 Point::Point()
@@ -61,7 +60,7 @@ Point::Point(const Point& pt)
 
 /////////////////////////////////
 
-clip2tri::clip2tri()
+clip2tri::clip2tri() : openSubject(false)
 {
    // Do nothing!
 }
@@ -85,79 +84,95 @@ void clip2tri::triangulate(const vector<vector<Point> > &inputPolygons, vector<P
    triangulateComplex(outputTriangles, bounds, solution);
 }
 
-IntPoint clip2tri::intPoint(double x, double y)
-{
-    return IntPoint(S64(x * CLIPPER_SCALE_FACT_D), S64(y * CLIPPER_SCALE_FACT_D));
-}
-
-PointD clip2tri::pointD(IntPoint p)
-{
-    return PointD(F64(p.X) * CLIPPER_SCALE_FACT_INVERSE_D, F64(p.Y) * CLIPPER_SCALE_FACT_INVERSE_D);
-}
-
-void clip2tri::addClipPolygon(const std::vector<IntPoint> &path)
+void clip2tri::addClipPolygon(const Path &path)
 {
     try  // prevent any exception to spill into Qt
     {
-        if (path.front() != path.back())
-            return; // Clip polygons must be closed.
         clipper.AddPath(path, ptClip, true);
     }
-    catch(...)
+    catch(ClipperLib::clipperException &e)
     {
-       printf("addClipPolygon: clipper.AddPath, something went wrong\n");
+        printf("addClipPolygon: %s\n", e.what());
     }
 }
 
-void clip2tri::addSubjectPath(const std::vector<IntPoint> &path, bool closed)
+void clip2tri::addSubjectPath(const Path &path, bool closed)
 {
     try  // prevent any exception to spill into Qt
     {
-        if (path.front() != path.back() && closed)
-            return; // Clip polygons must be closed.
         clipper.AddPath(path, ptSubject, closed);
     }
-    catch(...)
+    catch(ClipperLib::clipperException &e)
     {
-       printf("addSubjectPath: clipper.AddPath, something went wrong\n");
+        printf("addSubjectPath: %s\n", e.what());
+        return;
     }
+    if (!closed)
+        openSubject = true;
 }
 
 void clip2tri::clearClipper()
 {
     // clear doesn't throw
     clipper.Clear();
+    openSubject = false;
 }
 
-Paths clip2tri::executeUnion(PolyFillType subjFillType, PolyFillType clipFillType)
+static ClipperLib::ClipType operation(const clip2tri::Operation &op)
 {
-    Paths solution;
-    try  // prevent any exception to spill into Qt
-    {
-        clipper.Execute(ctUnion, solution, subjFillType, subjFillType);
+    switch (op) {
+    case clip2tri::Intersection:
+        return ClipperLib::ctIntersection;
+    case clip2tri::Union:
+        return ClipperLib::ctUnion;
+    case clip2tri::Difference:
+        return ClipperLib::ctDifference;
+    case clip2tri::Xor:
+        return ClipperLib::ctXor;
     }
-    catch(...)
-    {
-       printf("executeUnion: clipper.Execute, something went wrong\n");
+    return ctIntersection;
+}
+
+static std::string operationName(const clip2tri::Operation &op)
+{
+    switch (op) {
+    case clip2tri::Intersection:
+        return std::string("Intersection");
+    case clip2tri::Union:
+        return std::string("Union");
+    case clip2tri::Difference:
+        return std::string("Difference");
+    case clip2tri::Xor:
+        return std::string("Xor");
     }
-    return solution;
+    return std::string("Intersection");
 }
 
-Paths clip2tri::executeIntersection(PolyFillType subjFillType, PolyFillType clipFillType)
+Paths clip2tri::execute(const clip2tri::Operation op, const PolyFillType subjFillType, const PolyFillType clipFillType)
 {
     Paths solution;
-    try  // prevent any exception to spill into Qt
+    try  // prevent any exception from spilling into Qt
     {
-        clipper.Execute(ctIntersection, solution, subjFillType, subjFillType);
+        if (!openSubject) {
+            clipper.Execute(operation(op), solution, subjFillType, clipFillType);
+        } else {
+            PolyTree res;
+            clipper.Execute(operation(op), res, subjFillType, clipFillType);
+            PolyNode *n = res.GetFirst();
+            if (n) {
+                solution.push_back(n->Contour);
+                while ((n = n->GetNext()))
+                    solution.push_back(n->Contour);
+            }
+        }
     }
-    catch(...)
+    catch(ClipperLib::clipperException &e)
     {
-       printf("executeIntersection: clipper.Execute, something went wrong\n");
+        printf("executing %s: %s\n", operationName(op).c_str(), e.what());
     }
     return solution;
 }
 
-
 Path clip2tri::upscaleClipperPoints(const vector<Point> &inputPolygon)
 {
    Path outputPolygon;
@@ -222,9 +237,9 @@ bool clip2tri::mergePolysToPolyTree(const vector<vector<Point> > &inputPolygons,
    {
       clipper.AddPaths(input, ptSubject, true);
    }
-   catch(...)
+   catch(ClipperLib::clipperException &e)
    {
-      printf("clipper.AddPaths, something went wrong\n");
+       printf("mergePolysToPolyTree: %s\n", e.what());
    }
 
    return clipper.Execute(ctUnion, solution, pftNonZero, pftNonZero);
diff --git a/src/3rdparty/clip2tri/clip2tri.h b/src/3rdparty/clip2tri/clip2tri.h
index a94bb6a1..37b563bb 100644
--- a/src/3rdparty/clip2tri/clip2tri.h
+++ b/src/3rdparty/clip2tri/clip2tri.h
@@ -30,7 +30,7 @@
 #define CLIP2TRI_H_
 
 #include <vector>
-#include "../clipper/clipper.h"
+#include <clipper.h>
 
 using namespace std;
 using namespace ClipperLib;
@@ -57,18 +57,6 @@ struct Point
    Point(T in_x, U in_y) { x = static_cast<F32>(in_x); y = static_cast<F32>(in_y); }
 };
 
-struct PointD
-{
-   F64 x;
-   F64 y;
-
-   PointD();
-   PointD(const PointD &pt);
-
-   template<class T, class U>
-   PointD(T in_x, U in_y) { x = static_cast<F64>(in_x); y = static_cast<F64>(in_y); }
-};
-
 class clip2tri
 {
 private:
@@ -85,29 +73,26 @@ private:
          const PolyTree &polyTree, bool ignoreFills = true, bool ignoreHoles = false);
 
 public:
+   enum Operation { Union, Intersection, Difference, Xor };
    clip2tri();
    virtual ~clip2tri();
 
    void triangulate(const vector<vector<Point> > &inputPolygons, vector<Point> &outputTriangles,
          const vector<Point> &boundingPolygon);
 
-   inline static IntPoint intPoint(double x, double y);
-   inline static PointD   pointD(IntPoint p);
-
-   // Clip polygons MUST be closed. Meaning path[0] == path[path.size()-1]
-   void addClipPolygon(const std::vector<IntPoint> &path);
+   // Clip polygons are intended as closed, even if the first and last vertex aren't the same.
+   void addClipPolygon(const Path &path);
    // Closed means the path has to be effectively closed. Meaning path[0] == path[path.size()-1]
-   void addSubjectPath(const std::vector<IntPoint> &path, bool closed);
+   void addSubjectPath(const Path &path, bool closed);
 
    void clearClipper();
 
-   Paths executeUnion(PolyFillType subjFillType = pftEvenOdd,
-                      PolyFillType clipFillType = pftEvenOdd);
-
-   Paths executeIntersection(PolyFillType subjFillType = pftEvenOdd,
-                             PolyFillType clipFillType = pftEvenOdd);
+   Paths execute(const Operation op,
+                 const PolyFillType subjFillType = pftNonZero,
+                 const PolyFillType clipFillType = pftNonZero);
 
    Clipper clipper;
+   bool openSubject;
 };
 
 } /* namespace c2t */
diff --git a/src/3rdparty/clip2tri/clip2tri.pro b/src/3rdparty/clip2tri/clip2tri.pro
index 50901c06..4ae7a799 100644
--- a/src/3rdparty/clip2tri/clip2tri.pro
+++ b/src/3rdparty/clip2tri/clip2tri.pro
@@ -2,6 +2,9 @@ TARGET = clip2tri
 
 CONFIG += staticlib exceptions
 
+INCLUDEPATH += ../poly2tri
+INCLUDEPATH += ../clipper
+
 load(qt_helper_lib)
 
 # workaround for QTBUG-31586