[core] Fix up v1 vector tile geometries with clipper

4 files changed, 76 insertions, 1 deletions

diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp
index 2e3d0576db..f58c96ddea 100644
--- a/src/mbgl/tile/geometry_tile.cpp
+++ b/src/mbgl/tile/geometry_tile.cpp
@@ -1,6 +1,8 @@
 #include <mbgl/tile/geometry_tile.hpp>
 #include <mbgl/tile/tile_id.hpp>
 
+#include <clipper/clipper.hpp>
+
 namespace mbgl {
 
 static double signedArea(const GeometryCoordinates& ring) {
@@ -15,6 +17,67 @@ static double signedArea(const GeometryCoordinates& ring) {
     return sum;
 }
 
+static ClipperLib::Path toClipperPath(const GeometryCoordinates& ring) {
+    ClipperLib::Path result;
+    result.reserve(ring.size());
+    for (const auto& p : ring) {
+        result.emplace_back(p.x, p.y);
+    }
+    return result;
+}
+
+static GeometryCoordinates fromClipperPath(const ClipperLib::Path& path) {
+    GeometryCoordinates result;
+    result.reserve(path.size());
+    for (const auto& p : path) {
+        using Coordinate = GeometryCoordinates::coordinate_type;
+        assert(p.x >= std::numeric_limits<Coordinate>::min());
+        assert(p.x <= std::numeric_limits<Coordinate>::max());
+        assert(p.y >= std::numeric_limits<Coordinate>::min());
+        assert(p.y <= std::numeric_limits<Coordinate>::max());
+        result.emplace_back(Coordinate(p.x), Coordinate(p.y));
+    }
+    return result;
+}
+
+static void processPolynodeBranch(ClipperLib::PolyNode* polynode, GeometryCollection& rings) {
+    // Exterior ring.
+    rings.push_back(fromClipperPath(polynode->Contour));
+    assert(signedArea(rings.back()) > 0);
+
+    // Interior rings.
+    for (auto * ring : polynode->Childs) {
+        rings.push_back(fromClipperPath(ring->Contour));
+        assert(signedArea(rings.back()) < 0);
+    }
+
+    // PolyNodes may be nested in the case of a polygon inside a hole.
+    for (auto * ring : polynode->Childs) {
+        for (auto * subRing : ring->Childs) {
+            processPolynodeBranch(subRing, rings);
+        }
+    }
+}
+
+GeometryCollection fixupPolygons(const GeometryCollection& rings) {
+    ClipperLib::Clipper clipper;
+    clipper.StrictlySimple(true);
+
+    for (const auto& ring : rings) {
+        clipper.AddPath(toClipperPath(ring), ClipperLib::ptSubject, true);
+    }
+
+    ClipperLib::PolyTree polygons;
+    clipper.Execute(ClipperLib::ctUnion, polygons, ClipperLib::pftEvenOdd, ClipperLib::pftEvenOdd);
+    clipper.Clear();
+
+    GeometryCollection result;
+    for (auto * polynode : polygons.Childs) {
+        processPolynodeBranch(polynode, result);
+    }
+    return result;
+}
+
 std::vector<GeometryCollection> classifyRings(const GeometryCollection& rings) {
     std::vector<GeometryCollection> polygons;
 
diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp
index 347d21e62c..2e51b4edc8 100644
--- a/src/mbgl/tile/geometry_tile.hpp
+++ b/src/mbgl/tile/geometry_tile.hpp
@@ -94,4 +94,8 @@ std::vector<GeometryCollection> classifyRings(const GeometryCollection&);
 // convert from GeometryTileFeature to Feature (eventually we should eliminate GeometryTileFeature)
 Feature convertFeature(const GeometryTileFeature&, const CanonicalTileID&);
 
+// Fix up possibly-non-V2-compliant polygon geometry using angus clipper.
+// The result is guaranteed to have correctly wound, strictly simple rings.
+GeometryCollection fixupPolygons(const GeometryCollection&);
+
 } // namespace mbgl
diff --git a/src/mbgl/tile/vector_tile.cpp b/src/mbgl/tile/vector_tile.cpp
index 343224052a..4af6a12271 100644
--- a/src/mbgl/tile/vector_tile.cpp
+++ b/src/mbgl/tile/vector_tile.cpp
@@ -152,7 +152,11 @@ GeometryCollection VectorTileFeature::getGeometries() const {
         }
     }
 
-    return lines;
+    if (layer.version >= 2 || type != FeatureType::Polygon) {
+        return lines;
+    }
+
+    return fixupPolygons(lines);
 }
 
 VectorTile::VectorTile(std::shared_ptr<const std::string> data_)
@@ -195,6 +199,9 @@ VectorTileLayer::VectorTileLayer(protozero::pbf_reader layer_pbf) {
         case 5: // extent
             extent = layer_pbf.get_uint32();
             break;
+        case 15: // version
+            version = layer_pbf.get_uint32();
+            break;
         default:
             layer_pbf.skip();
             break;
diff --git a/src/mbgl/tile/vector_tile.hpp b/src/mbgl/tile/vector_tile.hpp
index aed7b7ee03..9e81f0ec8c 100644
--- a/src/mbgl/tile/vector_tile.hpp
+++ b/src/mbgl/tile/vector_tile.hpp
@@ -46,6 +46,7 @@ private:
     friend class VectorTileFeature;
 
     std::string name;
+    uint32_t version = 1;
     uint32_t extent = 4096;
     std::map<std::string, uint32_t> keysMap;
     std::vector<std::reference_wrapper<const std::string>> keys;