Better describe the streaming tilecover algorithm in comments

2 files changed, 57 insertions, 22 deletions

diff --git a/src/mbgl/util/tile_cover_impl.cpp b/src/mbgl/util/tile_cover_impl.cpp
index 2fac8b239d..f796cc7bd3 100644
--- a/src/mbgl/util/tile_cover_impl.cpp
+++ b/src/mbgl/util/tile_cover_impl.cpp
@@ -17,8 +17,7 @@ struct TileSpan {
     bool winding;
 };
 
-
-// Find the first local minimum going forward in the list.
+// Reorder a ring of points such that it starts at a point with a local minimum y-coordinate
 void start_list_on_local_minimum(PointList& points) {
     auto prev_pt = std::prev(points.end(), 2);
     auto pt = points.begin();
@@ -42,6 +41,8 @@ void start_list_on_local_minimum(PointList& points) {
 }
 
 //Create a bound towards a local maximum point, starting from pt.
+// Traverse from current pt until the next pt changes y-direction, and copy
+// all points from start to end (inclusive) into a Bound.
 Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) {
     if (std::distance(pt, points.end()) < 2) { return {}; }
 
@@ -50,7 +51,7 @@ Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) {
     while (pt->y <= next_pt->y) {
         pt++;
         next_pt++;
-        if(next_pt == points.end()) { pt++; break; }
+        if (next_pt == points.end()) { pt++; break; }
     }
 
     const auto pt_distance = std::distance(begin, next_pt);
@@ -66,6 +67,8 @@ Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) {
 }
 
 //Create a bound towards a local minimum point, starting from pt.
+// Traverse from current pt until the next pt changes y-direction, and copy
+// all points from start to end (inclusive) into a Bound.
 Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) {
     if (std::distance(pt, points.end()) < 2) { return {}; }
 
@@ -74,7 +77,7 @@ Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) {
     while (pt->y > next_pt->y) {
         pt++;
         next_pt++;
-        if(next_pt == points.end()) { pt++; break; }
+        if (next_pt == points.end()) { pt++; break; }
     }
 
     const auto pt_distance = std::distance(begin, next_pt);
@@ -89,10 +92,14 @@ Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) {
     return bnd;
 }
 
-//Build a map of bounds and their starting Y tile coordinate.
+// Given a set of points (ring or list) representing a shape, compute a set of
+// Bounds, where each Bound represents edges going from a local minima to a local
+// maxima point. The BoundsMap is an edge table indexed on the starting Y-tile
+// of each Bound.
 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
+    //While traversing closed rings, start the bounds at a local minimum.
+    // (For linestrings the starting point is always a local maxima/minima)
     if (closed) {
         start_list_on_local_minimum(points);
     }
@@ -120,12 +127,16 @@ void update_span(TileSpan& xp, double 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) {
+// Use the active bounds, an accumulation of all bounds that enter the y tile row,
+// or start in that row.
+// Iterate all points of a bound until it exits the row (or ends) and compute the
+// set of X tiles it spans across. The winding direction of the bound is also
+// captured for each span to later fill tiles between bounds for polygons
+std::vector<TileSpan> scan_row(uint32_t y, Bounds& activeBounds) {
     std::vector<TileSpan> tile_range;
-    tile_range.reserve(aet.size());
+    tile_range.reserve(activeBounds.size());
 
-    for(Bound& b: aet) {
+    for(Bound& b: activeBounds) {
         TileSpan xp = { INT_MAX, 0, b.winding };
         double x;
         const auto numEdges = b.points.size() - 1;
@@ -140,7 +151,7 @@ std::vector<TileSpan> scan_row(uint32_t y, Bounds& aet) {
                 x = b.interpolate(y+1);
                 update_span(xp, x);
                 break;
-            } else if(b.currentPoint == numEdges - 1) {
+            } 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);
@@ -151,11 +162,11 @@ std::vector<TileSpan> scan_row(uint32_t y, Bounds& aet) {
     }
     // 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()) {
+    auto bound = activeBounds.begin();
+    while (bound != activeBounds.end()) {
         if ( bound->currentPoint == bound->points.size() - 1 &&
             bound->points[bound->currentPoint].y <= y+1) {
-            bound = aet.erase(bound);
+            bound = activeBounds.erase(bound);
         } else {
             bound++;
         }
@@ -195,7 +206,7 @@ struct BuildBoundsMap {
     BoundsMap operator()(const Point<double>&p) const {
         Bound bnd;
         auto point = p;
-        if(project) {
+        if (project) {
             point = Projection::project(LatLng{p.y, p.x}, zoom);
         }
         bnd.points.insert(bnd.points.end(), 2, point);
@@ -211,7 +222,7 @@ struct BuildBoundsMap {
         for (const Point<double>& p: points) {
             Bound bnd;
             auto point = p;
-            if(project) {
+            if (project) {
                 point = Projection::project(LatLng{p.y, p.x}, zoom);
             }
             bnd.points.insert(bnd.points.end(), 2, point);
@@ -272,20 +283,26 @@ TileCover::Impl::Impl(int32_t z, const Geometry<double>& geom, bool project)
     tileX = tileXSpans.front().first;
 }
 
+// Aggregate all Bounds that start in or enter into the next tileY row. Multi-geoms
+// may have discontinuity in the BoundMap, so skip forward to the next tileY row
+// when the current/next row has no more bounds in it.
+// Use scan_row to generate the tileX spans. Merge spans to avoid duplicate tiles
+// in TileCoverImpl::next(). For closed geometry, use the non-zero rule to expand
+// (fill) tiles between pairs of spans.
 void TileCover::Impl::nextRow() {
-    // Update AET for next row
+    // Update activeBounds 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));
+            std::move(currentBounds->second.begin(), currentBounds->second.end(),
+                std::back_inserter(activeBounds));
             currentBounds++;
         }
     }
-    //Scan aet and update currenRange with x_min, x_max pairs
+    //Scan the active bounds and update currentRange with x_min, x_max pairs
     auto xps = util::scan_row(tileY, activeBounds);
     if (xps.size() == 0) {
         return;
@@ -309,7 +326,9 @@ void TileCover::Impl::nextRow() {
 }
 
 bool TileCover::Impl::hasNext() const {
-    return (!tileXSpans.empty() && tileX < tileXSpans.front().second && tileY < (1u << zoom));
+    return (!tileXSpans.empty()
+            && tileX < tileXSpans.front().second
+            && tileY < (1u << zoom));
 }
 
 optional<UnwrappedTileID> TileCover::Impl::next() {
@@ -320,7 +339,7 @@ optional<UnwrappedTileID> TileCover::Impl::next() {
     tileX++;
     if (tileX >= tileXSpans.front().second) {
         tileXSpans.pop();
-        if(tileXSpans.empty()) {
+        if (tileXSpans.empty()) {
             tileY++;
             nextRow();
         }
diff --git a/src/mbgl/util/tile_cover_impl.hpp b/src/mbgl/util/tile_cover_impl.hpp
index 7c16718984..e9c06e44aa 100644
--- a/src/mbgl/util/tile_cover_impl.hpp
+++ b/src/mbgl/util/tile_cover_impl.hpp
@@ -60,6 +60,22 @@ struct Bound {
     }
 };
 
+// Implements a modified scan-line algorithm to provide a streaming interface for
+// tile cover on arbitrary shapes.
+// A `BoundsMap` is genereted from the input geometry where each tuple indicates
+// the set of Bounds that start at a y tile coordinate. Each bound represents
+// a chain of edges from a local y-minima to a local y-maxima.
+// For each row, the activeBounds list aggregates all bounds that enter into or
+// begin in that row. This running list of bounds is scanned, capturing the
+// x-coordinates spanned by edges in a bound until the bound exits the row (or
+// ends). The result is a set of (possibly overlapping) min,max pairs of x coordinates
+// (spans). In the simplest case a span represents the x-coordinates at which a
+// single edge intersects the top and bottom of a tile row. Interior tiles of a
+// polygon are captured by merging spans using the non-zero rule.
+// The result of a scan using `nextRow()` is a list of spans (tileXSpans) of x-coordinates
+// that includes edges and interiors of polygons.
+// next() returns a tileID for each x-coordinate from (first, second] in each
+// span in tileXSpans.
 class TileCover::Impl {
 public:
     Impl(int32_t z, const Geometry<double>& geom, bool project = true);