[core] Add classifyRings

2 files changed, 57 insertions, 0 deletions

diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp
new file mode 100644
index 0000000000..9f57c7ab6f
--- /dev/null
+++ b/src/mbgl/tile/geometry_tile.cpp
@@ -0,0 +1,54 @@
+#include <mbgl/tile/geometry_tile.hpp>
+#include <mbgl/tile/tile_id.hpp>
+
+namespace mbgl {
+
+static double signedArea(const GeometryCoordinates& ring) {
+    double sum = 0;
+
+    for (std::size_t i = 0, len = ring.size(), j = len - 1; i < len; j = i++) {
+        const GeometryCoordinate& p1 = ring[i];
+        const GeometryCoordinate& p2 = ring[j];
+        sum += (p2.x - p1.x) * (p1.y + p2.y);
+    }
+
+    return sum;
+}
+
+std::vector<GeometryCollection> classifyRings(const GeometryCollection& rings) {
+    std::vector<GeometryCollection> polygons;
+
+    std::size_t len = rings.size();
+
+    if (len <= 1) {
+        polygons.push_back(rings);
+        return polygons;
+    }
+
+    GeometryCollection polygon;
+    int8_t ccw = 0;
+
+    for (std::size_t i = 0; i < len; i++) {
+        double area = signedArea(rings[i]);
+
+        if (area == 0)
+            continue;
+
+        if (ccw == 0)
+            ccw = (area < 0 ? -1 : 1);
+
+        if (ccw == (area < 0 ? -1 : 1) && !polygon.empty()) {
+            polygons.push_back(polygon);
+            polygon.clear();
+        }
+
+        polygon.push_back(rings[i]);
+    }
+
+    if (!polygon.empty())
+        polygons.push_back(polygon);
+
+    return polygons;
+}
+
+} // namespace mbgl
diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp
index 4db5d4dbeb..edbe91b6c9 100644
--- a/src/mbgl/tile/geometry_tile.hpp
+++ b/src/mbgl/tile/geometry_tile.hpp
@@ -87,6 +87,9 @@ public:
     virtual std::unique_ptr<AsyncRequest> monitorTile(const Callback&) = 0;
 };
 
+// classifies an array of rings into polygons with outer rings and holes
+std::vector<GeometryCollection> classifyRings(const GeometryCollection&);
+
 } // namespace mbgl
 
 #endif