Implement per-tile strreaming. Cleanup and rename types and member variables. Move elements out of the boundsMap into the activeBounds (instead of copy).

5 files changed, 212 insertions, 165 deletions

diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index d15257a3f1..488e6b88ce 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -12,6 +12,8 @@ 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 {
@@ -31,7 +33,7 @@ struct edge {
 };
 
 // scan-line conversion
-static void scanSpans(edge e0, edge e1, int32_t ymin, int32_t ymax, util::ScanLine scanLine) {
+static void scanSpans(edge e0, edge e1, int32_t ymin, int32_t ymax, ScanLine scanLine) {
     double y0 = ::fmax(ymin, std::floor(e1.y0));
     double y1 = ::fmin(ymax, std::ceil(e1.y1));
 
@@ -55,7 +57,7 @@ static void scanSpans(edge e0, edge e1, int32_t ymin, int32_t ymax, util::ScanLi
 }
 
 // scan-line conversion
-static void scanTriangle(const Point<double>& a, const Point<double>& b, const Point<double>& c, int32_t ymin, int32_t ymax, util::ScanLine& scanLine) {
+static void scanTriangle(const Point<double>& a, const Point<double>& b, const Point<double>& c, int32_t ymin, int32_t ymax, ScanLine& scanLine) {
     edge ab = edge(a, b);
     edge bc = edge(b, c);
     edge ca = edge(c, a);
@@ -171,27 +173,12 @@ std::vector<UnwrappedTileID> tileCover(const TransformState& state, int32_t z) {
 }
 
 std::vector<UnwrappedTileID> tileCover(const Geometry<double>& geometry, int32_t z) {
-    struct ID {
-        int32_t x, y;
-    };
-
-    std::list<ID> t;
-    auto scanCover = [&](int32_t x0, int32_t x1, int32_t y) {
-        for (auto x = x0; x < x1; x++) {
-            t.emplace_back(ID{ x, y });
-        }
-    };
-
+    std::vector<UnwrappedTileID> result;
     TileCover tc(geometry, z, true);
-    while (tc.next()) {
-        tc.getTiles(scanCover);
+    while (tc.hasNext()) {
+        result.push_back(*tc.next());
     };
 
-    std::vector<UnwrappedTileID> result;
-    result.reserve(t.size());
-    for (const auto& id : t) {
-        result.emplace_back(z, id.x, id.y);
-    }
     return result;
 }
 
@@ -216,16 +203,11 @@ uint64_t tileCount(const LatLngBounds& bounds, uint8_t zoom){
 }
 
 uint64_t tileCount(const Geometry<double>& geometry, uint8_t z) {
-    uint64_t tileCount;
-    auto scanCover = [&](int32_t x0, int32_t x1, int32_t) {
-        for (auto x = x0; x < x1; x++) {
-            tileCount+= (x1 - x0);
-        }
-    };
+    uint64_t tileCount = 0;
 
     TileCover tc(geometry, z, true);
     while (tc.next()) {
-        tc.getTiles(scanCover);
+        tileCount++;
     };
     return tileCount;
 }
@@ -258,12 +240,12 @@ TileCover::~TileCover() {
 
 }
 
-bool TileCover::next() {
+optional<UnwrappedTileID> TileCover::next() {
     return impl->next();
 }
 
-bool TileCover::getTiles(ScanLine& scanCover) {
-    return impl->scanRow(scanCover);
+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 f851096dd3..c953d764d2 100644
--- a/src/mbgl/util/tile_cover.hpp
+++ b/src/mbgl/util/tile_cover.hpp
@@ -3,6 +3,7 @@
 #include <mbgl/tile/tile_id.hpp>
 #include <mbgl/style/types.hpp>
 #include <mbgl/util/geometry.hpp>
+#include <mbgl/util/optional.hpp>
 
 #include <vector>
 #include <memory>
@@ -14,8 +15,6 @@ class LatLngBounds;
 
 namespace util {
 
-using ScanLine = const std::function<void(int32_t x0, int32_t x1, int32_t y)>;
-
 // Helper class to stream tile-cover results per row
 class TileCover {
 public:
@@ -24,11 +23,8 @@ public:
     TileCover(const Geometry<double>&, int32_t z, bool project = true);
     ~TileCover();
 
-    //Returns false when there are no more rows to cover
-    bool next();
-    //Invokes the ScanLine callback to indicate tiles coverd for the row from [x0,x1)
-    // ScanLine may be invoked with duplcaite or overlapping ranges.
-    bool getTiles(ScanLine&);
+    optional<UnwrappedTileID> next();
+    bool hasNext();
 
 private:
     class Impl;
diff --git a/src/mbgl/util/tile_cover_impl.cpp b/src/mbgl/util/tile_cover_impl.cpp
index 97f10dfb4e..c571f684b3 100644
--- a/src/mbgl/util/tile_cover_impl.cpp
+++ b/src/mbgl/util/tile_cover_impl.cpp
@@ -1,4 +1,5 @@
 #include <mbgl/util/tile_cover_impl.hpp>
+#include <mbgl/util/tile_coordinate.hpp>
 
 #include <functional>
 #include <cmath>
@@ -9,9 +10,16 @@
 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) {
-    assert(points.size() > 2);
-    // Find the first local minimum going forward in the list
     auto prev_pt = std::prev(points.end(), 2);
     auto pt = points.begin();
     auto next_pt = std::next(pt);
@@ -25,18 +33,27 @@ void start_list_on_local_minimum(PointList& points) {
         next_pt++;
         if (next_pt == points.end()) { next_pt = std::next(points.begin()); }
     }
-    //Re-close the linear ring
-    points.pop_back();
+    //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 (points[0].y < points[1].y) std::copy(pt, points.end(), std::back_inserter(bnd.points));
-        else std::reverse_copy(pt, points.end(), std::back_inserter(bnd.points));
+        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;
     }
@@ -62,12 +79,19 @@ Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) {
     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));
-        else std::reverse_copy(pt, points.end(), std::back_inserter(bnd.points));
+        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;
     }
@@ -88,89 +112,98 @@ Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) {
     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;
 }
 
-void build_edge_table(PointList& points, uint32_t maxTile, EdgeTable& et, bool closed = false) {
+//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 due to double precision
+            // 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(std::move(to_max));
+            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(std::move(to_min));
+            et[y].push_back(to_min);
         }
     }
     assert(pointsIter == points.end());
 }
 
-std::vector<TileCoverRange> scan_row(uint32_t y, BoundList& aet) {
-    std::vector<TileCoverRange> tile_range;
+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) {
-        TileCoverRange xp = { INT_MAX, 0 , b.winding };
+        TileSpan xp = { INT_MAX, 0, b.winding };
         double x;
         const auto numEdges = b.points.size() - 1;
         assert(numEdges >= 1);
-        while (b.currentPointIndex < numEdges) {
+        while (b.currentPoint < numEdges) {
             x = b.interpolate(y);
-            xp.x0 = std::min(xp.x0, static_cast<int32_t>(std::floor(x)));
-            xp.x1 = std::max(xp.x1, static_cast<int32_t>(std::ceil(x)));
+            update_span(xp, x);
 
-            // If this edge ends beyond the current row, find the x-value at the exit,
-            //  and be done with this bound
-            auto& p1 = b.points[b.currentPointIndex + 1];
+            // 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);
-                xp.x0 = std::min(xp.x0, static_cast<int32_t>(std::floor(x)));
-                xp.x1 = std::max(xp.x1, static_cast<int32_t>(std::ceil(x)));
+                update_span(xp, x);
                 break;
-            } else if(b.currentPointIndex == numEdges - 1) {
-                // For last edge, consider x at edge end;
+            } else if(b.currentPoint == numEdges - 1) {
+                // For last edge, consider x-intercept at the end of the edge.
                 x = p1.x;
-                xp.x0 = std::min(xp.x0, static_cast<int32_t>(std::floor(x)));
-                xp.x1 = std::max(xp.x1, static_cast<int32_t>(std::ceil(x)));
+                update_span(xp, x);
             }
-            b.currentPointIndex++;
+            b.currentPoint++;
         }
         tile_range.push_back(xp);
     }
-    // Erase bounds in aet whose current edge ends inside this row, or there are no more edges
+    // 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->currentPointIndex == bound->points.size() - 1 &&
-            bound->points[bound->currentPointIndex].y <= y+1) {
+        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(), [] (TileCoverRange& a, TileCoverRange& b) {
-        return std::tie(a.x0, a.x1) < std::tie(b.x0, b.x1);
+    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 ToEdgeTable {
+struct BuildBoundsMap {
     int32_t zoom;
     bool project = false;
-    ToEdgeTable(int32_t z, bool p): zoom(z), project(p) {}
+    BuildBoundsMap(int32_t z, bool p): zoom(z), project(p) {}
 
-    void buildTable(const std::vector<Point<double>>& points, EdgeTable& et, bool closed = false) const {
+    void buildTable(const std::vector<Point<double>>& points, BoundsMap& et, bool closed = false) const {
         PointList projectedPoints;
         if (project) {
             projectedPoints.reserve(points.size());
@@ -181,15 +214,15 @@ struct ToEdgeTable {
         } else {
             projectedPoints.insert(projectedPoints.end(), points.begin(), points.end());
         }
-        build_edge_table(projectedPoints, 1 << zoom, et, closed);
+        build_bounds_map(projectedPoints, 1 << zoom, et, closed);
     }
 
-    void buildPolygonTable(const Polygon<double>& polygon, EdgeTable& et) const {
+    void buildPolygonTable(const Polygon<double>& polygon, BoundsMap& et) const {
         for(const auto&ring : polygon) {
             buildTable(ring, et, true);
         }
     }
-    EdgeTable operator()(const Point<double>&p) const {
+    BoundsMap operator()(const Point<double>&p) const {
         Bound bnd;
         auto point = p;
         if(project) {
@@ -197,14 +230,14 @@ struct ToEdgeTable {
         }
         bnd.points.insert(bnd.points.end(), 2, point);
         bnd.winding = false;
-        EdgeTable et;
+        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;
     }
 
-    EdgeTable operator()(const MultiPoint<double>& points) const {
-        EdgeTable et;
+    BoundsMap operator()(const MultiPoint<double>& points) const {
+        BoundsMap et;
         for (const Point<double>& p: points) {
             Bound bnd;
             auto point = p;
@@ -219,97 +252,113 @@ struct ToEdgeTable {
         return et;
     }
 
-    EdgeTable operator()(const LineString<double>& lines) const {
-        EdgeTable et;
+    BoundsMap operator()(const LineString<double>& lines) const {
+        BoundsMap et;
         buildTable(lines, et);
         return et;
     }
 
-    EdgeTable operator()(const MultiLineString<double>& lines) const {
-        EdgeTable et;
+    BoundsMap operator()(const MultiLineString<double>& lines) const {
+        BoundsMap et;
         for(const auto&line : lines) {
             buildTable(line, et);
         }
         return et;
     }
 
-    EdgeTable operator()(const Polygon<double>& polygon) const {
-        EdgeTable et;
+    BoundsMap operator()(const Polygon<double>& polygon) const {
+        BoundsMap et;
         buildPolygonTable(polygon, et);
         return et;
     }
 
-    EdgeTable operator()(const MultiPolygon<double>& polygons) const {
-        EdgeTable et;
+    BoundsMap operator()(const MultiPolygon<double>& polygons) const {
+        BoundsMap et;
         for(const auto& polygon: polygons) {
             buildPolygonTable(polygon, et);
         }
         return et;
     }
 
-    EdgeTable operator()(const mapbox::geometry::geometry_collection<double>&) const {
+    BoundsMap operator()(const mapbox::geometry::geometry_collection<double>&) const {
         return {};
     }
 };
 
-TileCover::Impl::Impl(int32_t z, const Geometry<double>& geom, bool project): maxY(1 << z) {
+TileCover::Impl::Impl(int32_t z, const Geometry<double>& geom, bool project)
+ : zoom(z) {
     ToFeatureType toFeatureType;
     isClosed = apply_visitor(toFeatureType, geom) == FeatureType::Polygon;
 
-    ToEdgeTable toEdgeTable(z, project);
-    edgeTable = apply_visitor(toEdgeTable, geom);
-    reset();
-}
-
-void TileCover::Impl::reset() {
-    if (edgeTable.size() == 0) return;
-    currentEdgeTable = edgeTable.begin();
-    activeEdgeTable = currentEdgeTable->second;
-    currentRow = currentEdgeTable->first;
-}
+    BuildBoundsMap toBoundsMap(z, project);
+    boundsMap = apply_visitor(toBoundsMap, geom);
+    if (boundsMap.size() == 0) return;
 
-bool TileCover::Impl::next() {
-    return activeEdgeTable.size() != 0 && currentRow < maxY;
+    //Iniitalize the active edge table, and current row span
+    currentBounds = boundsMap.begin();
+    tileY = 0;
+    nextRow();
+    if (tileXSpans.empty()) return;
+    tileX = tileXSpans.front().first;
 }
 
-bool TileCover::Impl::scanRow(ScanLine& scanCover) {
-    if (!next()) { return false; }
-
-    auto xps = util::scan_row(currentRow, activeEdgeTable);
-    assert(isClosed ? xps.size() % 2 == 0 : true);
+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].x0;
-    auto x_max = xps[0].x1;
+    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.x0 >= x_max) {
-                scanCover(x_min, x_max, currentRow);
-                x_min = xp.x0;
+            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.x1);
+        x_max = std::max(x_min, xp.xmax);
     }
-    scanCover(x_min, x_max, currentRow);
-    assert(isClosed ? nzRule == 0 : true);
+    tileXSpans.emplace(x_min, x_max);
+}
 
-    // Update AET for next row
-    currentRow++;
-    auto nextRow = std::next(currentEdgeTable);
-    if (nextRow != edgeTable.end()) {
-        if (activeEdgeTable.size() == 0 && nextRow->first > currentRow) {
-            //For multi-geoms: Use the next row with an edge table starting point
-            currentRow = nextRow->first;
+bool TileCover::Impl::hasNext() const {
+    return (!tileXSpans.empty() && tileX < tileXSpans.front().second && tileY < (1 << 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 (currentRow == nextRow->first) {
-            activeEdgeTable.insert(activeEdgeTable.end(), nextRow->second.begin(), nextRow->second.end());
-            currentEdgeTable++;
+        if (!tileXSpans.empty()) {
+            tileX = tileXSpans.front().first;
         }
     }
-    return next();
-
+    return UnwrappedTileID(zoom, x, y);
 }
 
 } // namespace util
diff --git a/src/mbgl/util/tile_cover_impl.hpp b/src/mbgl/util/tile_cover_impl.hpp
index 6210cbd108..7c16718984 100644
--- a/src/mbgl/util/tile_cover_impl.hpp
+++ b/src/mbgl/util/tile_cover_impl.hpp
@@ -1,12 +1,12 @@
 #pragma once
 
 #include <mbgl/util/tile_cover.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 <map>
+#include <queue>
 
 namespace mbgl {
 
@@ -17,29 +17,33 @@ namespace util {
 
 struct Bound;
 
-using PointList = std::vector<Point<double>>;
-using BoundList = std::vector<Bound>;
-using EdgeTable = std::map<uint32_t, BoundList>;
-struct TileCoverRange {
-    int32_t x0;
-    int32_t x1;
-    bool winding;
-};
-    
+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 {
-    PointList points;
-    size_t currentPointIndex = 0;
+    std::vector<Point<double>> points;
+    size_t currentPoint = 0;
     bool winding = false;
+
     Bound() = default;
     Bound(const Bound& rhs) {
         points = rhs.points;
-        currentPointIndex = rhs.currentPointIndex;
+        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[currentPointIndex];
-        const auto& p1 = points[currentPointIndex + 1];
+        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;
@@ -56,25 +60,31 @@ struct Bound {
     }
 };
 
-using ScanLine = const std::function<void(int32_t x0, int32_t x1, int32_t y)>;
-
 class TileCover::Impl {
-
 public:
     Impl(int32_t z, const Geometry<double>& geom, bool project = true);
     ~Impl() = default;
-    bool scanRow(ScanLine& );
-    bool next();
-    void reset();
+
+    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;
-    uint32_t currentRow;
-    BoundList activeEdgeTable;
-    EdgeTable edgeTable;
-    EdgeTable::iterator currentEdgeTable;
-    const uint32_t maxY;
-};
 
+    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
diff --git a/test/util/tile_cover.test.cpp b/test/util/tile_cover.test.cpp
index ddba3fa0f1..7defa761af 100644
--- a/test/util/tile_cover.test.cpp
+++ b/test/util/tile_cover.test.cpp
@@ -67,11 +67,9 @@ TEST(TileCoverStream, Arctic) {
     util::TileCover tc(bounds, zoom);
     auto results = util::tileCover(bounds, zoom);
     std::vector<UnwrappedTileID> t;
-    while(tc.getTiles([&](int32_t x0, int32_t x1, int32_t y) {
-        for (auto x = x0; x < x1; x++) {
-            t.emplace_back(zoom, x, y);
-        }
-    })) {};
+    while(tc.hasNext()) {
+            t.push_back(*tc.next());
+    };
     EXPECT_EQ(t.size(), results.size());
 }
 
@@ -79,11 +77,9 @@ TEST(TileCoverStream, WorldZ1) {
     auto zoom = 1;
     util::TileCover tc(LatLngBounds::world(), zoom);
     std::vector<UnwrappedTileID> t;
-    while(tc.getTiles([&](int32_t x0, int32_t x1, int32_t y) {
-        for (auto x = x0; x < x1; x++) {
-            t.emplace_back(zoom, x, y);
-        }
-    })){};
+    while(tc.hasNext()) {
+        t.push_back(*tc.next());
+    };
     EXPECT_EQ((std::vector<UnwrappedTileID>{
         { 1, 0, 0 }, { 1, 1, 0 }, { 1, 0, 1 }, { 1, 1, 1 },
     }), t);
@@ -263,6 +259,20 @@ TEST(TileCover, GeomSanFranciscoPoly) {
     }), util::tileCover(sanFranciscoGeom, 12));
 }
 
+TEST(TileCover, GeomInvalid) {
+    auto point = Point<double>{ -122.5744, 97.6609 };
+    EXPECT_THROW(util::tileCover(point, 2), std::domain_error);
+
+    auto badPoly = Polygon<double> { { {1.0,  35.0} } };
+    EXPECT_EQ((std::vector<UnwrappedTileID>{ }), util::tileCover(badPoly, 16));
+
+    //Should handle open polygons.
+    badPoly = Polygon<double> { { {1.0,  34.2}, {1.0, 34.4}, {0.5, 34.3} } };
+    EXPECT_EQ((std::vector<UnwrappedTileID>{
+        { 10, 513, 407 }, { 10, 514, 407},
+        { 10, 513, 408 }, { 10, 514, 408}
+    }), util::tileCover(badPoly, 10));
+}
 
 
 TEST(TileCount, World) {