diff options
author | Asheem Mamoowala <asheem.mamoowala@mapbox.com> | 2018-05-16 17:18:17 -0700 |
---|---|---|
committer | Asheem Mamoowala <asheem.mamoowala@mapbox.com> | 2018-07-16 17:11:03 -0700 |
commit | 15019425bef4d486d1de068be53649056375bc5e (patch) | |
tree | 294d4b15c9ff3b93b1101e3a063cc87006244e84 /src/mbgl/util/tile_cover_impl.hpp | |
parent | b2ff57c09c19c4364039673cffafd929c88a8b89 (diff) | |
download | qtlocation-mapboxgl-15019425bef4d486d1de068be53649056375bc5e.tar.gz |
Better describe the streaming tilecover algorithm in comments
Diffstat (limited to 'src/mbgl/util/tile_cover_impl.hpp')
-rw-r--r-- | src/mbgl/util/tile_cover_impl.hpp | 16 |
1 files changed, 16 insertions, 0 deletions
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); |