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

3 files changed, 19 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&);