1 #include <mbgl/util/tile_cover.hpp>
2 #include <mbgl/util/constants.hpp>
3 #include <mbgl/util/interpolate.hpp>
4 #include <mbgl/map/transform_state.hpp>
5 #include <mbgl/util/tile_cover_impl.hpp>
6 #include <mbgl/util/tile_coordinate.hpp>
7 #include <mbgl/math/log2.hpp>
8 
9 #include <functional>
10 #include <list>
11 
12 namespace mbgl {
13 
14 namespace {
15 
16 using ScanLine = const std::function<void(int32_t x0, int32_t x1, int32_t y)>;
17 
18 // Taken from polymaps src/Layer.js
19 // https://github.com/simplegeo/polymaps/blob/master/src/Layer.js#L333-L383
20 struct edge {
21     double x0 = 0, y0 = 0;
22     double x1 = 0, y1 = 0;
23     double dx = 0, dy = 0;
24 
edgembgl::__anon8821e1f70111::edge25     edge(Point<double> a, Point<double> b) {
26         if (a.y > b.y) std::swap(a, b);
27         x0 = a.x;
28         y0 = a.y;
29         x1 = b.x;
30         y1 = b.y;
31         dx = b.x - a.x;
32         dy = b.y - a.y;
33     }
34 };
35 
36 // scan-line conversion
scanSpans(edge e0,edge e1,int32_t ymin,int32_t ymax,ScanLine scanLine)37 static void scanSpans(edge e0, edge e1, int32_t ymin, int32_t ymax, ScanLine scanLine) {
38     double y0 = ::fmax(ymin, std::floor(e1.y0));
39     double y1 = ::fmin(ymax, std::ceil(e1.y1));
40 
41     // sort edges by x-coordinate
42     if ((e0.x0 == e1.x0 && e0.y0 == e1.y0) ?
43         (e0.x0 + e1.dy / e0.dy * e0.dx < e1.x1) :
44         (e0.x1 - e1.dy / e0.dy * e0.dx < e1.x0)) {
45         std::swap(e0, e1);
46     }
47 
48     // scan lines!
49     double m0 = e0.dx / e0.dy;
50     double m1 = e1.dx / e1.dy;
51     double d0 = e0.dx > 0; // use y + 1 to compute x0
52     double d1 = e1.dx < 0; // use y + 1 to compute x1
53     for (int32_t y = y0; y < y1; y++) {
54         double x0 = m0 * ::fmax(0, ::fmin(e0.dy, y + d0 - e0.y0)) + e0.x0;
55         double x1 = m1 * ::fmax(0, ::fmin(e1.dy, y + d1 - e1.y0)) + e1.x0;
56         scanLine(std::floor(x1), std::ceil(x0), y);
57     }
58 }
59 
60 // scan-line conversion
scanTriangle(const Point<double> & a,const Point<double> & b,const Point<double> & c,int32_t ymin,int32_t ymax,ScanLine & scanLine)61 static void scanTriangle(const Point<double>& a, const Point<double>& b, const Point<double>& c, int32_t ymin, int32_t ymax, ScanLine& scanLine) {
62     edge ab = edge(a, b);
63     edge bc = edge(b, c);
64     edge ca = edge(c, a);
65 
66     // sort edges by y-length
67     if (ab.dy > bc.dy) { std::swap(ab, bc); }
68     if (ab.dy > ca.dy) { std::swap(ab, ca); }
69     if (bc.dy > ca.dy) { std::swap(bc, ca); }
70 
71     // scan span! scan span!
72     if (ab.dy) scanSpans(ca, ab, ymin, ymax, scanLine);
73     if (bc.dy) scanSpans(ca, bc, ymin, ymax, scanLine);
74 }
75 
76 } // namespace
77 
78 namespace util {
79 
80 namespace {
81 
tileCover(const Point<double> & tl,const Point<double> & tr,const Point<double> & br,const Point<double> & bl,const Point<double> & c,int32_t z)82 std::vector<UnwrappedTileID> tileCover(const Point<double>& tl,
83                                        const Point<double>& tr,
84                                        const Point<double>& br,
85                                        const Point<double>& bl,
86                                        const Point<double>& c,
87                                        int32_t z) {
88     const int32_t tiles = 1 << z;
89 
90     struct ID {
91         int32_t x, y;
92         double sqDist;
93     };
94 
95     std::vector<ID> t;
96 
97     auto scanLine = [&](int32_t x0, int32_t x1, int32_t y) {
98         int32_t x;
99         if (y >= 0 && y <= tiles) {
100             for (x = x0; x < x1; ++x) {
101                 const auto dx = x + 0.5 - c.x, dy = y + 0.5 - c.y;
102                 t.emplace_back(ID{ x, y, dx * dx + dy * dy });
103             }
104         }
105     };
106 
107     // Divide the screen up in two triangles and scan each of them:
108     // \---+
109     // | \ |
110     // +---\.
111     scanTriangle(tl, tr, br, 0, tiles, scanLine);
112     scanTriangle(br, bl, tl, 0, tiles, scanLine);
113 
114     // Sort first by distance, then by x/y.
115     std::sort(t.begin(), t.end(), [](const ID& a, const ID& b) {
116         return std::tie(a.sqDist, a.x, a.y) < std::tie(b.sqDist, b.x, b.y);
117     });
118 
119     // Erase duplicate tile IDs (they typically occur at the common side of both triangles).
120     t.erase(std::unique(t.begin(), t.end(), [](const ID& a, const ID& b) {
121                 return a.x == b.x && a.y == b.y;
122             }), t.end());
123 
124     std::vector<UnwrappedTileID> result;
125     for (const auto& id : t) {
126         result.emplace_back(z, id.x, id.y);
127     }
128     return result;
129 }
130 
131 } // namespace
132 
coveringZoomLevel(double zoom,style::SourceType type,uint16_t size)133 int32_t coveringZoomLevel(double zoom, style::SourceType type, uint16_t size) {
134     zoom += ::log2(util::tileSize / size);
135     if (type == style::SourceType::Raster || type == style::SourceType::Video) {
136         return ::round(zoom);
137     } else {
138         return std::floor(zoom);
139     }
140 }
141 
tileCover(const LatLngBounds & bounds_,int32_t z)142 std::vector<UnwrappedTileID> tileCover(const LatLngBounds& bounds_, int32_t z) {
143     if (bounds_.isEmpty() ||
144         bounds_.south() >  util::LATITUDE_MAX ||
145         bounds_.north() < -util::LATITUDE_MAX) {
146         return {};
147     }
148 
149     LatLngBounds bounds = LatLngBounds::hull(
150         { std::max(bounds_.south(), -util::LATITUDE_MAX), bounds_.west() },
151         { std::min(bounds_.north(),  util::LATITUDE_MAX), bounds_.east() });
152 
153     return tileCover(
154         Projection::project(bounds.northwest(), z),
155         Projection::project(bounds.northeast(), z),
156         Projection::project(bounds.southeast(), z),
157         Projection::project(bounds.southwest(), z),
158         Projection::project(bounds.center(), z),
159         z);
160 }
161 
tileCover(const TransformState & state,int32_t z)162 std::vector<UnwrappedTileID> tileCover(const TransformState& state, int32_t z) {
163     assert(state.valid());
164 
165     const double w = state.getSize().width;
166     const double h = state.getSize().height;
167     return tileCover(
168         TileCoordinate::fromScreenCoordinate(state, z, { 0,   0   }).p,
169         TileCoordinate::fromScreenCoordinate(state, z, { w,   0   }).p,
170         TileCoordinate::fromScreenCoordinate(state, z, { w,   h   }).p,
171         TileCoordinate::fromScreenCoordinate(state, z, { 0,   h   }).p,
172         TileCoordinate::fromScreenCoordinate(state, z, { w/2, h/2 }).p,
173         z);
174 }
175 
tileCover(const Geometry<double> & geometry,int32_t z)176 std::vector<UnwrappedTileID> tileCover(const Geometry<double>& geometry, int32_t z) {
177     std::vector<UnwrappedTileID> result;
178     TileCover tc(geometry, z, true);
179     while (tc.hasNext()) {
180         result.push_back(*tc.next());
181     };
182 
183     return result;
184 }
185 
186 // Taken from https://github.com/mapbox/sphericalmercator#xyzbbox-zoom-tms_style-srs
187 // Computes the projected tiles for the lower left and upper right points of the bounds
188 // and uses that to compute the tile cover count
tileCount(const LatLngBounds & bounds,uint8_t zoom)189 uint64_t tileCount(const LatLngBounds& bounds, uint8_t zoom){
190     if (zoom == 0) {
191         return 1;
192     }
193     auto sw = Projection::project(bounds.southwest(), zoom);
194     auto ne = Projection::project(bounds.northeast(), zoom);
195     auto maxTile = std::pow(2.0, zoom);
196     auto x1 = floor(sw.x);
197     auto x2 = ceil(ne.x) - 1;
198     auto y1 = util::clamp(floor(sw.y), 0.0, maxTile - 1);
199     auto y2 = util::clamp(floor(ne.y), 0.0, maxTile - 1);
200 
201     auto dx = x1 > x2 ? (maxTile - x1) + x2 : x2 - x1;
202     auto dy = y1 - y2;
203     return (dx + 1) * (dy + 1);
204 }
205 
tileCount(const Geometry<double> & geometry,uint8_t z)206 uint64_t tileCount(const Geometry<double>& geometry, uint8_t z) {
207     uint64_t tileCount = 0;
208 
209     TileCover tc(geometry, z, true);
210     while (tc.next()) {
211         tileCount++;
212     };
213     return tileCount;
214 }
215 
TileCover(const LatLngBounds & bounds_,int32_t z)216 TileCover::TileCover(const LatLngBounds&bounds_, int32_t z) {
217     LatLngBounds bounds = LatLngBounds::hull(
218         { std::max(bounds_.south(), -util::LATITUDE_MAX), bounds_.west() },
219         { std::min(bounds_.north(),  util::LATITUDE_MAX), bounds_.east() });
220 
221     if (bounds.isEmpty() ||
222         bounds.south() >  util::LATITUDE_MAX ||
223         bounds.north() < -util::LATITUDE_MAX) {
224         bounds = LatLngBounds::world();
225     }
226 
227     auto sw = Projection::project(bounds.southwest(), z);
228     auto ne = Projection::project(bounds.northeast(), z);
229     auto se = Projection::project(bounds.southeast(), z);
230     auto nw = Projection::project(bounds.northwest(), z);
231 
232     Polygon<double> p({ {sw, nw, ne, se, sw} });
233     impl = std::make_unique<TileCover::Impl>(z, p, false);
234 }
235 
TileCover(const Geometry<double> & geom,int32_t z,bool project)236 TileCover::TileCover(const Geometry<double>& geom, int32_t z, bool project/* = true*/)
237  : impl( std::make_unique<TileCover::Impl>(z, geom, project)) {
238 }
239 
~TileCover()240 TileCover::~TileCover() {
241 
242 }
243 
next()244 optional<UnwrappedTileID> TileCover::next() {
245     return impl->next();
246 }
247 
hasNext()248 bool TileCover::hasNext() {
249     return impl->hasNext();
250 }
251 
252 } // namespace util
253 } // namespace mbgl
254