1 #pragma once
2 
3 #include <mbgl/util/tile_cover.hpp>
4 #include <mbgl/util/geometry.hpp>
5 #include <mbgl/util/optional.hpp>
6 
7 #include <vector>
8 #include <map>
9 #include <queue>
10 
11 namespace mbgl {
12 
13 class TransformState;
14 class LatLngBounds;
15 
16 namespace util {
17 
18 struct Bound;
19 
20 using Bounds = std::vector<Bound>;
21 using BoundsMap = std::map<uint32_t, Bounds>;
22 
23 // A chain of points from a local minimum to a local maximum. `winding` indicates
24 //  the direction of the original geometry.
25 struct Bound {
26     std::vector<Point<double>> points;
27     size_t currentPoint = 0;
28     bool winding = false;
29 
30     Bound() = default;
Boundmbgl::util::Bound31     Bound(const Bound& rhs) {
32         points = rhs.points;
33         currentPoint = rhs.currentPoint;
34         winding = rhs.winding;
35     }
operator =mbgl::util::Bound36     Bound& operator=(Bound&& rhs) {
37         points = std::move(rhs.points);
38         currentPoint = rhs.currentPoint;
39         winding = rhs.winding;
40         return *this;
41     }
42 
43     // Compute the interpolated x coordinate at y for the current edge
interpolatembgl::util::Bound44     double interpolate(uint32_t y) {
45         const auto& p0 = points[currentPoint];
46         const auto& p1 = points[currentPoint + 1];
47 
48         const auto dx = p1.x - p0.x;
49         const auto dy = p1.y - p0.y;
50         auto x = p0.x;
51         if (dx == 0) {
52             return x;
53         } else if (dy == 0){
54             return y <= p0.y ? p0.x : p1.x;
55         }
56         if (y < p0.y) return x;
57         if (y > p1.y) return p1.x;
58         x = (dx / dy) * (y - p0.y) + p0.x;
59         return x;
60     }
61 };
62 
63 // Implements a modified scan-line algorithm to provide a streaming interface for
64 // tile cover on arbitrary shapes.
65 // A `BoundsMap` is genereted from the input geometry where each tuple indicates
66 // the set of Bounds that start at a y tile coordinate. Each bound represents
67 // a chain of edges from a local y-minima to a local y-maxima.
68 // For each row, the activeBounds list aggregates all bounds that enter into or
69 // begin in that row. This running list of bounds is scanned, capturing the
70 // x-coordinates spanned by edges in a bound until the bound exits the row (or
71 // ends). The result is a set of (possibly overlapping) min,max pairs of x coordinates
72 // (spans). In the simplest case a span represents the x-coordinates at which a
73 // single edge intersects the top and bottom of a tile row. Interior tiles of a
74 // polygon are captured by merging spans using the non-zero rule.
75 // The result of a scan using `nextRow()` is a list of spans (tileXSpans) of x-coordinates
76 // that includes edges and interiors of polygons.
77 // next() returns a tileID for each x-coordinate from (first, second] in each
78 // span in tileXSpans.
79 class TileCover::Impl {
80 public:
81     Impl(int32_t z, const Geometry<double>& geom, bool project = true);
82     ~Impl() = default;
83 
84     optional<UnwrappedTileID> next();
85     bool hasNext() const;
86 
87 private:
88     using TileSpans = std::queue<std::pair<int32_t, int32_t>>;
89 
90     void nextRow();
91 
92     const int32_t zoom;
93     bool isClosed;
94 
95     BoundsMap boundsMap;
96     BoundsMap::iterator currentBounds;
97     // List of bounds that begin at or before `tileY`
98     Bounds activeBounds;
99 
100     TileSpans tileXSpans;
101     uint32_t tileY;
102     int32_t tileX;
103 };
104 
105 } // namespace util
106 } // namespace mbgl
107