[core] Don't earcut more than 500 inner rings

5 files changed, 81 insertions, 1 deletions

diff --git a/src/mbgl/renderer/fill_bucket.cpp b/src/mbgl/renderer/fill_bucket.cpp
index ed8f70059a..967a2df8c3 100644
--- a/src/mbgl/renderer/fill_bucket.cpp
+++ b/src/mbgl/renderer/fill_bucket.cpp
@@ -35,7 +35,10 @@ FillBucket::~FillBucket() {
 }
 
 void FillBucket::addGeometry(const GeometryCollection& geometry) {
-    for (const auto& polygon : classifyRings(geometry)) {
+    for (auto& polygon : classifyRings(geometry)) {
+        // Optimize polygons with many interior rings for earcut tesselation.
+        limitHoles(polygon, 500);
+
         std::size_t totalVertices = 0;
 
         for (const auto& ring : polygon) {
diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp
index f58c96ddea..f4589b4052 100644
--- a/src/mbgl/tile/geometry_tile.cpp
+++ b/src/mbgl/tile/geometry_tile.cpp
@@ -114,6 +114,18 @@ std::vector<GeometryCollection> classifyRings(const GeometryCollection& rings) {
     return polygons;
 }
 
+void limitHoles(GeometryCollection& polygon, uint32_t maxHoles) {
+    if (polygon.size() > 1 + maxHoles) {
+        std::nth_element(polygon.begin() + 1,
+                         polygon.begin() + 1 + maxHoles,
+                         polygon.end(),
+                         [] (const auto& a, const auto& b) {
+                             return signedArea(a) > signedArea(b);
+                         });
+        polygon.resize(1 + maxHoles);
+    }
+}
+
 static Feature::geometry_type convertGeometry(const GeometryTileFeature& geometryTileFeature, const CanonicalTileID& tileID) {
     const double size = util::EXTENT * std::pow(2, tileID.z);
     const double x0 = util::EXTENT * tileID.x;
diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp
index 2e51b4edc8..6904c922ba 100644
--- a/src/mbgl/tile/geometry_tile.hpp
+++ b/src/mbgl/tile/geometry_tile.hpp
@@ -91,6 +91,9 @@ public:
 // classifies an array of rings into polygons with outer rings and holes
 std::vector<GeometryCollection> classifyRings(const GeometryCollection&);
 
+// Truncate polygon to the largest `maxHoles` inner rings by area.
+void limitHoles(GeometryCollection&, uint32_t maxHoles);
+
 // convert from GeometryTileFeature to Feature (eventually we should eliminate GeometryTileFeature)
 Feature convertFeature(const GeometryTileFeature&, const CanonicalTileID&);
 
diff --git a/test/test.gypi b/test/test.gypi
index bf2d76536c..03052ab1c4 100644
--- a/test/test.gypi
+++ b/test/test.gypi
@@ -54,6 +54,7 @@
         'math/minmax.cpp',
         'math/clamp.cpp',
 
+        'tile/geometry_tile.cpp',
         'tile/tile_id.cpp',
 
         'storage/offline.cpp',
diff --git a/test/tile/geometry_tile.cpp b/test/tile/geometry_tile.cpp
new file mode 100644
index 0000000000..c94b20cee6
--- /dev/null
+++ b/test/tile/geometry_tile.cpp
@@ -0,0 +1,61 @@
+#include <mbgl/test/util.hpp>
+#include <mbgl/tile/geometry_tile.hpp>
+
+using namespace mbgl;
+
+TEST(GeometryTile, classifyRings1) {
+    std::vector<GeometryCollection> polygons = classifyRings({
+      { {0, 0}, {0, 40}, {40, 40}, {40, 0}, {0, 0} }
+    });
+
+    // output: 1 polygon
+    ASSERT_EQ(polygons.size(), 1);
+    // output: polygon 1 has 1 exterior
+    ASSERT_EQ(polygons[0].size(), 1);
+}
+
+TEST(GeometryTile, classifyRings2) {
+    std::vector<GeometryCollection> polygons = classifyRings({
+      { {0, 0}, {0, 40}, {40, 40}, {40, 0}, {0, 0} },
+      { {10, 10}, {20, 10}, {20, 20}, {10, 10} }
+    });
+
+    // output: 1 polygon
+    ASSERT_EQ(polygons.size(), 1);
+    // output: polygon 1 has 1 exterior, 1 interior
+    ASSERT_EQ(polygons[0].size(), 2);
+}
+
+TEST(GeometryTile, limitHoles1) {
+    GeometryCollection polygon = {
+      { {0, 0}, {0, 40}, {40, 40}, {40, 0}, {0, 0} },
+      { {30, 30}, {32, 30}, {32, 32}, {30, 30} },
+      { {10, 10}, {20, 10}, {20, 20}, {10, 10} }
+    };
+
+    limitHoles(polygon, 1);
+
+    // output: polygon 1 has 1 exterior, 1 interior
+    ASSERT_EQ(polygon.size(), 2);
+
+    // ensure we've kept the right rings (ones with largest areas)
+    ASSERT_EQ(polygon[0][0].x, 0);
+    ASSERT_EQ(polygon[1][0].x, 10);
+}
+
+TEST(GeometryTile, limitHoles2) {
+    GeometryCollection polygon = {
+      { {0, 0}, {0, 40}, {40, 40}, {40, 0}, {0, 0} },
+      { {10, 10}, {20, 10}, {20, 20}, {10, 10} },
+      { {30, 30}, {32, 30}, {32, 32}, {30, 30} }
+    };
+
+    limitHoles(polygon, 1);
+
+    // output: polygon 1 has 1 exterior, 1 interior
+    ASSERT_EQ(polygon.size(), 2);
+
+    // ensure we've kept the right rings (ones with largest areas)
+    ASSERT_EQ(polygon[0][0].x, 0);
+    ASSERT_EQ(polygon[1][0].x, 10);
+}