summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorAsheem Mamoowala <asheem.mamoowala@mapbox.com>2018-05-16 17:18:17 -0700
committerAsheem Mamoowala <asheem.mamoowala@mapbox.com>2018-07-16 17:11:03 -0700
commit15019425bef4d486d1de068be53649056375bc5e (patch)
tree294d4b15c9ff3b93b1101e3a063cc87006244e84 /src
parentb2ff57c09c19c4364039673cffafd929c88a8b89 (diff)
downloadqtlocation-mapboxgl-15019425bef4d486d1de068be53649056375bc5e.tar.gz
Better describe the streaming tilecover algorithm in comments
Diffstat (limited to 'src')
-rw-r--r--src/mbgl/util/tile_cover_impl.cpp63
-rw-r--r--src/mbgl/util/tile_cover_impl.hpp16
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);