[core] Streaming TileCover for polygonal regions (#11267)

A per-tile streaming algorithm for tile cover on points, lines, and polygons. Works for individual zoom levels, and not zoom ranges.

5 files changed, 559 insertions, 25 deletions

diff --git a/src/mbgl/renderer/layers/render_background_layer.cpp b/src/mbgl/renderer/layers/render_background_layer.cpp
index aebc4cc9aa..44c3fffb6c 100644
--- a/src/mbgl/renderer/layers/render_background_layer.cpp
+++ b/src/mbgl/renderer/layers/render_background_layer.cpp
@@ -7,6 +7,7 @@
 #include <mbgl/programs/programs.hpp>
 #include <mbgl/programs/background_program.hpp>
 #include <mbgl/util/tile_cover.hpp>
+#include <mbgl/map/transform_state.hpp>
 
 namespace mbgl {
 
diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index 39b562d811..488e6b88ce 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -2,13 +2,18 @@
 #include <mbgl/util/constants.hpp>
 #include <mbgl/util/interpolate.hpp>
 #include <mbgl/map/transform_state.hpp>
+#include <mbgl/util/tile_cover_impl.hpp>
+#include <mbgl/util/tile_coordinate.hpp>
 
 #include <functional>
+#include <list>
 
 namespace mbgl {
 
 namespace {
 
+using ScanLine = const std::function<void(int32_t x0, int32_t x1, int32_t y)>;
+
 // Taken from polymaps src/Layer.js
 // https://github.com/simplegeo/polymaps/blob/master/src/Layer.js#L333-L383
 struct edge {
@@ -27,8 +32,6 @@ struct edge {
     }
 };
 
-using ScanLine = const std::function<void(int32_t x0, int32_t x1, int32_t y)>;
-
 // scan-line conversion
 static void scanSpans(edge e0, edge e1, int32_t ymin, int32_t ymax, ScanLine scanLine) {
     double y0 = ::fmax(ymin, std::floor(e1.y0));
@@ -147,11 +150,11 @@ std::vector<UnwrappedTileID> tileCover(const LatLngBounds& bounds_, int32_t z) {
         { std::min(bounds_.north(),  util::LATITUDE_MAX), bounds_.east() });
 
     return tileCover(
-        TileCoordinate::fromLatLng(z, bounds.northwest()).p,
-        TileCoordinate::fromLatLng(z, bounds.northeast()).p,
-        TileCoordinate::fromLatLng(z, bounds.southeast()).p,
-        TileCoordinate::fromLatLng(z, bounds.southwest()).p,
-        TileCoordinate::fromLatLng(z, bounds.center()).p,
+        Projection::project(bounds.northwest(), z),
+        Projection::project(bounds.northeast(), z),
+        Projection::project(bounds.southeast(), z),
+        Projection::project(bounds.southwest(), z),
+        Projection::project(bounds.center(), z),
         z);
 }
 
@@ -169,25 +172,80 @@ std::vector<UnwrappedTileID> tileCover(const TransformState& state, int32_t z) {
         z);
 }
 
+std::vector<UnwrappedTileID> tileCover(const Geometry<double>& geometry, int32_t z) {
+    std::vector<UnwrappedTileID> result;
+    TileCover tc(geometry, z, true);
+    while (tc.hasNext()) {
+        result.push_back(*tc.next());
+    };
+
+    return result;
+}
+
 // Taken from https://github.com/mapbox/sphericalmercator#xyzbbox-zoom-tms_style-srs
 // Computes the projected tiles for the lower left and upper right points of the bounds
 // and uses that to compute the tile cover count
-uint64_t tileCount(const LatLngBounds& bounds, uint8_t zoom, uint16_t tileSize_){
-
-    auto sw = Projection::project(bounds.southwest().wrapped(), zoom, tileSize_);
-    auto ne = Projection::project(bounds.northeast().wrapped(), zoom, tileSize_);
-
-    auto x1 = floor(sw.x/ tileSize_);
-    auto x2 = floor((ne.x - 1) / tileSize_);
-    auto y1 = floor(sw.y/ tileSize_);
-    auto y2 = floor((ne.y - 1) / tileSize_);
-
-    auto minX = ::fmax(std::min(x1, x2), 0);
-    auto maxX = std::max(x1, x2);
-    auto minY = (std::pow(2, zoom) - 1) - std::max(y1, y2);
-    auto maxY = (std::pow(2, zoom) - 1) - ::fmax(std::min(y1, y2), 0);
-    
-    return (maxX - minX + 1) * (maxY - minY + 1);
+uint64_t tileCount(const LatLngBounds& bounds, uint8_t zoom){
+    if (zoom == 0) {
+        return 1;
+    }
+    auto sw = Projection::project(bounds.southwest(), zoom);
+    auto ne = Projection::project(bounds.northeast(), zoom);
+    auto maxTile = std::pow(2.0, zoom);
+    auto x1 = floor(sw.x);
+    auto x2 = ceil(ne.x) - 1;
+    auto y1 = util::clamp(floor(sw.y), 0.0, maxTile - 1);
+    auto y2 = util::clamp(floor(ne.y), 0.0, maxTile - 1);
+
+    auto dx = x1 > x2 ? (maxTile - x1) + x2 : x2 - x1;
+    auto dy = y1 - y2;
+    return (dx + 1) * (dy + 1);
+}
+
+uint64_t tileCount(const Geometry<double>& geometry, uint8_t z) {
+    uint64_t tileCount = 0;
+
+    TileCover tc(geometry, z, true);
+    while (tc.next()) {
+        tileCount++;
+    };
+    return tileCount;
+}
+
+TileCover::TileCover(const LatLngBounds&bounds_, int32_t z) {
+    LatLngBounds bounds = LatLngBounds::hull(
+        { std::max(bounds_.south(), -util::LATITUDE_MAX), bounds_.west() },
+        { std::min(bounds_.north(),  util::LATITUDE_MAX), bounds_.east() });
+
+    if (bounds.isEmpty() ||
+        bounds.south() >  util::LATITUDE_MAX ||
+        bounds.north() < -util::LATITUDE_MAX) {
+        bounds = LatLngBounds::world();
+    }
+
+    auto sw = Projection::project(bounds.southwest(), z);
+    auto ne = Projection::project(bounds.northeast(), z);
+    auto se = Projection::project(bounds.southeast(), z);
+    auto nw = Projection::project(bounds.northwest(), z);
+
+    Polygon<double> p({ {sw, nw, ne, se, sw} });
+    impl = std::make_unique<TileCover::Impl>(z, p, false);
+}
+
+TileCover::TileCover(const Geometry<double>& geom, int32_t z, bool project/* = true*/)
+ : impl( std::make_unique<TileCover::Impl>(z, geom, project)) {
+}
+
+TileCover::~TileCover() {
+
+}
+
+optional<UnwrappedTileID> TileCover::next() {
+    return impl->next();
+}
+
+bool TileCover::hasNext() {
+    return impl->hasNext();
 }
 
 } // namespace util
diff --git a/src/mbgl/util/tile_cover.hpp b/src/mbgl/util/tile_cover.hpp
index b2098b59b8..c953d764d2 100644
--- a/src/mbgl/util/tile_cover.hpp
+++ b/src/mbgl/util/tile_cover.hpp
@@ -2,9 +2,11 @@
 
 #include <mbgl/tile/tile_id.hpp>
 #include <mbgl/style/types.hpp>
-#include <mbgl/util/tile_coordinate.hpp>
+#include <mbgl/util/geometry.hpp>
+#include <mbgl/util/optional.hpp>
 
 #include <vector>
+#include <memory>
 
 namespace mbgl {
 
@@ -13,13 +15,31 @@ class LatLngBounds;
 
 namespace util {
 
+// Helper class to stream tile-cover results per row
+class TileCover {
+public:
+    TileCover(const LatLngBounds&, int32_t z);
+    // When project == true, projects the geometry points to tile coordinates
+    TileCover(const Geometry<double>&, int32_t z, bool project = true);
+    ~TileCover();
+
+    optional<UnwrappedTileID> next();
+    bool hasNext();
+
+private:
+    class Impl;
+    std::unique_ptr<Impl> impl;
+};
+
 int32_t coveringZoomLevel(double z, style::SourceType type, uint16_t tileSize);
 
 std::vector<UnwrappedTileID> tileCover(const TransformState&, int32_t z);
 std::vector<UnwrappedTileID> tileCover(const LatLngBounds&, int32_t z);
+std::vector<UnwrappedTileID> tileCover(const Geometry<double>&, int32_t z);
 
 // Compute only the count of tiles needed for tileCover
-uint64_t tileCount(const LatLngBounds&, uint8_t z, uint16_t tileSize);
+uint64_t tileCount(const LatLngBounds&, uint8_t z);
+uint64_t tileCount(const Geometry<double>&, uint8_t z);
 
 } // namespace util
 } // namespace mbgl
diff --git a/src/mbgl/util/tile_cover_impl.cpp b/src/mbgl/util/tile_cover_impl.cpp
new file mode 100644
index 0000000000..b3fc07f7dd
--- /dev/null
+++ b/src/mbgl/util/tile_cover_impl.cpp
@@ -0,0 +1,365 @@
+#include <mbgl/util/tile_cover_impl.hpp>
+#include <mbgl/util/tile_coordinate.hpp>
+
+#include <functional>
+#include <cmath>
+#include <assert.h>
+#include <limits.h>
+#include <algorithm>
+
+namespace mbgl {
+namespace util {
+
+using PointList = std::vector<Point<double>>;
+
+struct TileSpan {
+    int32_t xmin, xmax;
+    bool winding;
+};
+
+
+// Find the first local minimum going forward in the list.
+void start_list_on_local_minimum(PointList& points) {
+    auto prev_pt = std::prev(points.end(), 2);
+    auto pt = points.begin();
+    auto next_pt = std::next(pt);
+    while (pt != points.end()) {
+        if ((pt->y <= prev_pt->y) &&
+            (pt->y < next_pt->y)) {
+            break;
+        }
+        prev_pt = pt;
+        pt++;
+        next_pt++;
+        if (next_pt == points.end()) { next_pt = std::next(points.begin()); }
+    }
+    //Re-close linear rings with first_pt = last_pt
+    if (points.back() == points.front()) {
+        points.pop_back();
+    }
+    std::rotate(points.begin(), pt, points.end());
+    points.push_back(*points.begin());
+}
+
+//Create a bound towards a local maximum point, starting from pt.
+Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) {
+    if (std::distance(pt, points.end()) < 2) { return {}; }
+    if (std::distance(pt, points.end()) == 2) {
+        Bound bnd;
+        if (pt->y < std::next(pt)->y) {
+            std::copy(pt, points.end(), std::back_inserter(bnd.points));
+            bnd.winding = true;
+        }
+        else {
+            std::reverse_copy(pt, points.end(), std::back_inserter(bnd.points));
+            bnd.winding = false;
+        }
+        pt = points.end();
+        return bnd;
+    }
+    const auto begin = pt;
+    auto prev_pt = pt == points.begin() ? std::prev(points.end(), 2) : std::prev(pt);
+    auto next_pt = std::next(pt) == points.end() ? std::next(points.begin()) : std::next(pt);
+    while (pt != points.end()) {
+        if ((pt->y >= prev_pt->y) &&
+            (pt->y > next_pt->y )) {
+            break;
+        }
+        prev_pt = pt;
+        pt++;
+        next_pt++;
+        if (next_pt == points.end()) { next_pt = std::next(points.begin()); }
+    }
+
+    Bound bnd;
+    if (std::next(pt) == points.end()) { next_pt = points.end(); pt++; };
+    bnd.points.reserve(static_cast<std::size_t>(std::distance(begin, next_pt)));
+    std::copy(begin, next_pt, std::back_inserter(bnd.points));
+    bnd.winding = true;
+    return bnd;
+}
+
+//Create a bound towards a local minimum point, starting from pt.
+Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) {
+    if (std::distance(pt, points.end()) < 2) { return {}; }
+    if (std::distance(pt, points.end()) == 2) {
+        Bound bnd;
+        if (pt->y < std::next(pt)->y) {
+            std::copy(pt, points.end(), std::back_inserter(bnd.points));
+            bnd.winding = true;
+        }
+        else {
+            std::reverse_copy(pt, points.end(), std::back_inserter(bnd.points));
+            bnd.winding = false;
+        }
+        pt = points.end();
+        return bnd;
+    }
+    auto begin = pt;
+    auto prev_pt = pt == points.begin() ? std::prev(points.end(), 2) : std::prev(pt);
+    auto next_pt = std::next(pt) == points.end() ? std::next(points.begin()) : std::next(pt);
+    while (pt != points.end()) {
+        if ((pt->y <= prev_pt->y) &&
+            (pt->y < next_pt->y)) {
+            break;
+        }
+        prev_pt = pt;
+        pt++;
+        next_pt++;
+        if (next_pt == points.end()) { next_pt = std::next(points.begin()); }
+    }
+
+    Bound bnd;
+    if (std::next(pt) == points.end()) { next_pt = points.end(); pt++; };
+    bnd.points.reserve(static_cast<std::size_t>(std::distance(begin, next_pt)));
+    //For bounds that start at a max, reverse copy so that all bounds start at a min
+    std::reverse_copy(begin, next_pt, std::back_inserter(bnd.points));
+    bnd.winding = false;
+    return bnd;
+}
+
+//Build a map of bounds and their starting Y tile coordinate.
+void build_bounds_map(PointList& points, uint32_t maxTile, BoundsMap& et, bool closed = false) {
+    if (points.size() < 2) return;
+    //While traversing closed rings, start the bounds at a local minimum
+    if (closed) {
+        start_list_on_local_minimum(points);
+    }
+
+    auto pointsIter = points.begin();
+    while (pointsIter != points.end()) {
+        Bound to_max = create_bound_towards_maximum(points, pointsIter);
+        Bound to_min = create_bound_towards_minimum(points, pointsIter);
+
+        if (to_max.points.size() > 0) {
+            // Projections may result in values beyond the bounds, clamp to max tile coordinates
+            const auto y = static_cast<uint32_t>(std::floor(clamp(to_max.points.front().y, 0.0, (double)maxTile)));
+            et[y].push_back(to_max);
+        }
+        if (to_min.points.size() > 0) {
+            const auto y = static_cast<uint32_t>(std::floor(clamp(to_min.points.front().y, 0.0, (double)maxTile)));
+            et[y].push_back(to_min);
+        }
+    }
+    assert(pointsIter == points.end());
+}
+
+void update_span(TileSpan& xp, double x) {
+    xp.xmin = std::min(xp.xmin, static_cast<int32_t>(std::floor(x)));
+    xp.xmax = std::max(xp.xmax, static_cast<int32_t>(std::ceil(x)));
+}
+
+//Build a vector of X tile-coordinates spanned by each bound.
+std::vector<TileSpan> scan_row(uint32_t y, Bounds& aet) {
+    std::vector<TileSpan> tile_range;
+    tile_range.reserve(aet.size());
+
+    for(Bound& b: aet) {
+        TileSpan xp = { INT_MAX, 0, b.winding };
+        double x;
+        const auto numEdges = b.points.size() - 1;
+        assert(numEdges >= 1);
+        while (b.currentPoint < numEdges) {
+            x = b.interpolate(y);
+            update_span(xp, x);
+
+            // If this edge ends beyond the current row, find the x-intercept where
+            // it exits the row
+            auto& p1 = b.points[b.currentPoint + 1];
+            if (p1.y > y+1) {
+                x = b.interpolate(y+1);
+                update_span(xp, x);
+                break;
+            } else if(b.currentPoint == numEdges - 1) {
+                // For last edge, consider x-intercept at the end of the edge.
+                x = p1.x;
+                update_span(xp, x);
+            }
+            b.currentPoint++;
+        }
+        tile_range.push_back(xp);
+    }
+    // Erase bounds in the active table whose current edge ends inside this row,
+    // or there are no more edges
+    auto bound = aet.begin();
+    while (bound != aet.end()) {
+        if ( bound->currentPoint == bound->points.size() - 1 &&
+            bound->points[bound->currentPoint].y <= y+1) {
+            bound = aet.erase(bound);
+        } else {
+            bound++;
+        }
+    }
+    // Sort the X-extents of each crossing bound by x_min, x_max
+    std::sort(tile_range.begin(), tile_range.end(), [] (TileSpan& a, TileSpan& b) {
+        return std::tie(a.xmin, a.xmax) < std::tie(b.xmin, b.xmax);
+    });
+
+    return tile_range;
+}
+
+struct BuildBoundsMap {
+    int32_t zoom;
+    bool project = false;
+    BuildBoundsMap(int32_t z, bool p): zoom(z), project(p) {}
+
+    void buildTable(const std::vector<Point<double>>& points, BoundsMap& et, bool closed = false) const {
+        PointList projectedPoints;
+        if (project) {
+            projectedPoints.reserve(points.size());
+            for(const auto&p : points) {
+                projectedPoints.push_back(
+                    Projection::project(LatLng{ p.y, p.x }, zoom));
+            }
+        } else {
+            projectedPoints.insert(projectedPoints.end(), points.begin(), points.end());
+        }
+        build_bounds_map(projectedPoints, 1 << zoom, et, closed);
+    }
+
+    void buildPolygonTable(const Polygon<double>& polygon, BoundsMap& et) const {
+        for(const auto&ring : polygon) {
+            buildTable(ring, et, true);
+        }
+    }
+    BoundsMap operator()(const Point<double>&p) const {
+        Bound bnd;
+        auto point = p;
+        if(project) {
+            point = Projection::project(LatLng{p.y, p.x}, zoom);
+        }
+        bnd.points.insert(bnd.points.end(), 2, point);
+        bnd.winding = false;
+        BoundsMap et;
+        const auto y = static_cast<uint32_t>(std::floor(clamp(point.y, 0.0, (double)(1 << zoom))));
+        et[y].push_back(bnd);
+        return et;
+    }
+
+    BoundsMap operator()(const MultiPoint<double>& points) const {
+        BoundsMap et;
+        for (const Point<double>& p: points) {
+            Bound bnd;
+            auto point = p;
+            if(project) {
+                point = Projection::project(LatLng{p.y, p.x}, zoom);
+            }
+            bnd.points.insert(bnd.points.end(), 2, point);
+            bnd.winding = false;
+            const auto y = static_cast<uint32_t>(std::floor(clamp(point.y, 0.0, (double)(1 << zoom))));
+            et[y].push_back(bnd);
+        }
+        return et;
+    }
+
+    BoundsMap operator()(const LineString<double>& lines) const {
+        BoundsMap et;
+        buildTable(lines, et);
+        return et;
+    }
+
+    BoundsMap operator()(const MultiLineString<double>& lines) const {
+        BoundsMap et;
+        for(const auto&line : lines) {
+            buildTable(line, et);
+        }
+        return et;
+    }
+
+    BoundsMap operator()(const Polygon<double>& polygon) const {
+        BoundsMap et;
+        buildPolygonTable(polygon, et);
+        return et;
+    }
+
+    BoundsMap operator()(const MultiPolygon<double>& polygons) const {
+        BoundsMap et;
+        for(const auto& polygon: polygons) {
+            buildPolygonTable(polygon, et);
+        }
+        return et;
+    }
+
+    BoundsMap operator()(const mapbox::geometry::geometry_collection<double>&) const {
+        return {};
+    }
+};
+
+TileCover::Impl::Impl(int32_t z, const Geometry<double>& geom, bool project)
+ : zoom(z) {
+    ToFeatureType toFeatureType;
+    isClosed = apply_visitor(toFeatureType, geom) == FeatureType::Polygon;
+
+    BuildBoundsMap toBoundsMap(z, project);
+    boundsMap = apply_visitor(toBoundsMap, geom);
+    if (boundsMap.size() == 0) return;
+
+    //Iniitalize the active edge table, and current row span
+    currentBounds = boundsMap.begin();
+    tileY = 0;
+    nextRow();
+    if (tileXSpans.empty()) return;
+    tileX = tileXSpans.front().first;
+}
+
+void TileCover::Impl::nextRow() {
+    // Update AET for next row
+    if (currentBounds != boundsMap.end()) {
+        if (activeBounds.size() == 0 && currentBounds->first > tileY) {
+            //For multi-geoms: use the next row with an edge table starting point
+            tileY = currentBounds->first;
+        }
+        if (tileY == currentBounds->first) {
+            
+            std::move(currentBounds->second.begin(), currentBounds->second.end(), std::back_inserter(activeBounds));
+            currentBounds++;
+        }
+    }
+    //Scan aet and update currenRange with x_min, x_max pairs
+    auto xps = util::scan_row(tileY, activeBounds);
+    if (xps.size() == 0) {
+        return;
+    }
+
+    auto x_min = xps[0].xmin;
+    auto x_max = xps[0].xmax;
+    int32_t nzRule = xps[0].winding ? 1 : -1;
+    for (size_t i = 1; i < xps.size(); i++) {
+        auto xp = xps[i];
+        if (!(isClosed && nzRule != 0)) {
+            if (xp.xmin > x_max && xp.xmax >= x_max) {
+                tileXSpans.emplace(x_min, x_max);
+                x_min = xp.xmin;
+            }
+        }
+        nzRule += xp.winding ? 1 : -1;
+        x_max = std::max(x_min, xp.xmax);
+    }
+    tileXSpans.emplace(x_min, x_max);
+}
+
+bool TileCover::Impl::hasNext() const {
+    return (!tileXSpans.empty() && tileX < tileXSpans.front().second && tileY < (1u << zoom));
+}
+
+optional<UnwrappedTileID> TileCover::Impl::next() {
+    if (!hasNext()) return {};
+
+    const auto x = tileX;
+    const auto y = tileY;
+    tileX++;
+    if (tileX >= tileXSpans.front().second) {
+        tileXSpans.pop();
+        if(tileXSpans.empty()) {
+            tileY++;
+            nextRow();
+        }
+        if (!tileXSpans.empty()) {
+            tileX = tileXSpans.front().first;
+        }
+    }
+    return UnwrappedTileID(zoom, x, y);
+}
+
+} // namespace util
+} // namespace mbgl
diff --git a/src/mbgl/util/tile_cover_impl.hpp b/src/mbgl/util/tile_cover_impl.hpp
new file mode 100644
index 0000000000..7c16718984
--- /dev/null
+++ b/src/mbgl/util/tile_cover_impl.hpp
@@ -0,0 +1,90 @@
+#pragma once
+
+#include <mbgl/util/tile_cover.hpp>
+#include <mbgl/util/geometry.hpp>
+#include <mbgl/util/optional.hpp>
+
+#include <vector>
+#include <map>
+#include <queue>
+
+namespace mbgl {
+
+class TransformState;
+class LatLngBounds;
+
+namespace util {
+
+struct Bound;
+
+using Bounds = std::vector<Bound>;
+using BoundsMap = std::map<uint32_t, Bounds>;
+
+// A chain of points from a local minimum to a local maximum. `winding` indicates
+//  the direction of the original geometry.
+struct Bound {
+    std::vector<Point<double>> points;
+    size_t currentPoint = 0;
+    bool winding = false;
+
+    Bound() = default;
+    Bound(const Bound& rhs) {
+        points = rhs.points;
+        currentPoint = rhs.currentPoint;
+        winding = rhs.winding;
+    }
+    Bound& operator=(Bound&& rhs) {
+        points = std::move(rhs.points);
+        currentPoint = rhs.currentPoint;
+        winding = rhs.winding;
+        return *this;
+    }
+
+    // Compute the interpolated x coordinate at y for the current edge
+    double interpolate(uint32_t y) {
+        const auto& p0 = points[currentPoint];
+        const auto& p1 = points[currentPoint + 1];
+
+        const auto dx = p1.x - p0.x;
+        const auto dy = p1.y - p0.y;
+        auto x = p0.x;
+        if (dx == 0) {
+            return x;
+        } else if (dy == 0){
+            return y <= p0.y ? p0.x : p1.x;
+        }
+        if (y < p0.y) return x;
+        if (y > p1.y) return p1.x;
+        x = (dx / dy) * (y - p0.y) + p0.x;
+        return x;
+    }
+};
+
+class TileCover::Impl {
+public:
+    Impl(int32_t z, const Geometry<double>& geom, bool project = true);
+    ~Impl() = default;
+
+    optional<UnwrappedTileID> next();
+    bool hasNext() const;
+
+private:
+    using TileSpans = std::queue<std::pair<int32_t, int32_t>>;
+
+    void nextRow();
+
+    const int32_t zoom;
+    bool isClosed;
+
+    BoundsMap boundsMap;
+    BoundsMap::iterator currentBounds;
+    // List of bounds that begin at or before `tileY`
+    Bounds activeBounds;
+
+    TileSpans tileXSpans;
+    uint32_t tileY;
+    int32_t tileX;
+};
+
+} // namespace util
+} // namespace mbgl