diff options
Diffstat (limited to 'src/mbgl/util/tile_cover_impl.cpp')
| -rw-r--r-- | src/mbgl/util/tile_cover_impl.cpp | 365 |
1 files changed, 365 insertions, 0 deletions
diff --git a/src/mbgl/util/tile_cover_impl.cpp b/src/mbgl/util/tile_cover_impl.cpp new file mode 100644 index 0000000000..b3fc07f7dd --- /dev/null +++ b/src/mbgl/util/tile_cover_impl.cpp @@ -0,0 +1,365 @@ +#include <mbgl/util/tile_cover_impl.hpp> +#include <mbgl/util/tile_coordinate.hpp> + +#include <functional> +#include <cmath> +#include <assert.h> +#include <limits.h> +#include <algorithm> + +namespace mbgl { +namespace util { + +using PointList = std::vector<Point<double>>; + +struct TileSpan { + int32_t xmin, xmax; + bool winding; +}; + + +// Find the first local minimum going forward in the list. +void start_list_on_local_minimum(PointList& points) { + auto prev_pt = std::prev(points.end(), 2); + auto pt = points.begin(); + auto next_pt = std::next(pt); + while (pt != points.end()) { + if ((pt->y <= prev_pt->y) && + (pt->y < next_pt->y)) { + break; + } + prev_pt = pt; + pt++; + next_pt++; + if (next_pt == points.end()) { next_pt = std::next(points.begin()); } + } + //Re-close linear rings with first_pt = last_pt + if (points.back() == points.front()) { + points.pop_back(); + } + std::rotate(points.begin(), pt, points.end()); + points.push_back(*points.begin()); +} + +//Create a bound towards a local maximum point, starting from pt. +Bound create_bound_towards_maximum(PointList& points, PointList::iterator& pt) { + if (std::distance(pt, points.end()) < 2) { return {}; } + if (std::distance(pt, points.end()) == 2) { + Bound bnd; + if (pt->y < std::next(pt)->y) { + std::copy(pt, points.end(), std::back_inserter(bnd.points)); + bnd.winding = true; + } + else { + std::reverse_copy(pt, points.end(), std::back_inserter(bnd.points)); + bnd.winding = false; + } + pt = points.end(); + return bnd; + } + const auto begin = pt; + auto prev_pt = pt == points.begin() ? std::prev(points.end(), 2) : std::prev(pt); + auto next_pt = std::next(pt) == points.end() ? std::next(points.begin()) : std::next(pt); + while (pt != points.end()) { + if ((pt->y >= prev_pt->y) && + (pt->y > next_pt->y )) { + break; + } + prev_pt = pt; + pt++; + next_pt++; + if (next_pt == points.end()) { next_pt = std::next(points.begin()); } + } + + Bound bnd; + if (std::next(pt) == points.end()) { next_pt = points.end(); pt++; }; + bnd.points.reserve(static_cast<std::size_t>(std::distance(begin, next_pt))); + std::copy(begin, next_pt, std::back_inserter(bnd.points)); + bnd.winding = true; + return bnd; +} + +//Create a bound towards a local minimum point, starting from pt. +Bound create_bound_towards_minimum(PointList& points, PointList::iterator& pt) { + if (std::distance(pt, points.end()) < 2) { return {}; } + if (std::distance(pt, points.end()) == 2) { + Bound bnd; + if (pt->y < std::next(pt)->y) { + std::copy(pt, points.end(), std::back_inserter(bnd.points)); + bnd.winding = true; + } + else { + std::reverse_copy(pt, points.end(), std::back_inserter(bnd.points)); + bnd.winding = false; + } + pt = points.end(); + return bnd; + } + auto begin = pt; + auto prev_pt = pt == points.begin() ? std::prev(points.end(), 2) : std::prev(pt); + auto next_pt = std::next(pt) == points.end() ? std::next(points.begin()) : std::next(pt); + while (pt != points.end()) { + if ((pt->y <= prev_pt->y) && + (pt->y < next_pt->y)) { + break; + } + prev_pt = pt; + pt++; + next_pt++; + if (next_pt == points.end()) { next_pt = std::next(points.begin()); } + } + + Bound bnd; + if (std::next(pt) == points.end()) { next_pt = points.end(); pt++; }; + bnd.points.reserve(static_cast<std::size_t>(std::distance(begin, next_pt))); + //For bounds that start at a max, reverse copy so that all bounds start at a min + std::reverse_copy(begin, next_pt, std::back_inserter(bnd.points)); + bnd.winding = false; + return bnd; +} + +//Build a map of bounds and their starting Y tile coordinate. +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 + if (closed) { + start_list_on_local_minimum(points); + } + + auto pointsIter = points.begin(); + while (pointsIter != points.end()) { + Bound to_max = create_bound_towards_maximum(points, pointsIter); + Bound to_min = create_bound_towards_minimum(points, pointsIter); + + if (to_max.points.size() > 0) { + // Projections may result in values beyond the bounds, clamp to max tile coordinates + const auto y = static_cast<uint32_t>(std::floor(clamp(to_max.points.front().y, 0.0, (double)maxTile))); + et[y].push_back(to_max); + } + if (to_min.points.size() > 0) { + const auto y = static_cast<uint32_t>(std::floor(clamp(to_min.points.front().y, 0.0, (double)maxTile))); + et[y].push_back(to_min); + } + } + assert(pointsIter == points.end()); +} + +void update_span(TileSpan& xp, double x) { + xp.xmin = std::min(xp.xmin, static_cast<int32_t>(std::floor(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) { + std::vector<TileSpan> tile_range; + tile_range.reserve(aet.size()); + + for(Bound& b: aet) { + TileSpan xp = { INT_MAX, 0, b.winding }; + double x; + const auto numEdges = b.points.size() - 1; + assert(numEdges >= 1); + while (b.currentPoint < numEdges) { + x = b.interpolate(y); + update_span(xp, x); + + // If this edge ends beyond the current row, find the x-intercept where + // it exits the row + auto& p1 = b.points[b.currentPoint + 1]; + if (p1.y > y+1) { + x = b.interpolate(y+1); + update_span(xp, x); + break; + } 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); + } + b.currentPoint++; + } + tile_range.push_back(xp); + } + // 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()) { + if ( bound->currentPoint == bound->points.size() - 1 && + bound->points[bound->currentPoint].y <= y+1) { + bound = aet.erase(bound); + } else { + bound++; + } + } + // Sort the X-extents of each crossing bound by x_min, x_max + std::sort(tile_range.begin(), tile_range.end(), [] (TileSpan& a, TileSpan& b) { + return std::tie(a.xmin, a.xmax) < std::tie(b.xmin, b.xmax); + }); + + return tile_range; +} + +struct BuildBoundsMap { + int32_t zoom; + bool project = false; + BuildBoundsMap(int32_t z, bool p): zoom(z), project(p) {} + + void buildTable(const std::vector<Point<double>>& points, BoundsMap& et, bool closed = false) const { + PointList projectedPoints; + if (project) { + projectedPoints.reserve(points.size()); + for(const auto&p : points) { + projectedPoints.push_back( + Projection::project(LatLng{ p.y, p.x }, zoom)); + } + } else { + projectedPoints.insert(projectedPoints.end(), points.begin(), points.end()); + } + build_bounds_map(projectedPoints, 1 << zoom, et, closed); + } + + void buildPolygonTable(const Polygon<double>& polygon, BoundsMap& et) const { + for(const auto&ring : polygon) { + buildTable(ring, et, true); + } + } + BoundsMap operator()(const Point<double>&p) const { + Bound bnd; + auto point = p; + if(project) { + point = Projection::project(LatLng{p.y, p.x}, zoom); + } + bnd.points.insert(bnd.points.end(), 2, point); + bnd.winding = false; + BoundsMap et; + const auto y = static_cast<uint32_t>(std::floor(clamp(point.y, 0.0, (double)(1 << zoom)))); + et[y].push_back(bnd); + return et; + } + + BoundsMap operator()(const MultiPoint<double>& points) const { + BoundsMap et; + for (const Point<double>& p: points) { + Bound bnd; + auto point = p; + if(project) { + point = Projection::project(LatLng{p.y, p.x}, zoom); + } + bnd.points.insert(bnd.points.end(), 2, point); + bnd.winding = false; + const auto y = static_cast<uint32_t>(std::floor(clamp(point.y, 0.0, (double)(1 << zoom)))); + et[y].push_back(bnd); + } + return et; + } + + BoundsMap operator()(const LineString<double>& lines) const { + BoundsMap et; + buildTable(lines, et); + return et; + } + + BoundsMap operator()(const MultiLineString<double>& lines) const { + BoundsMap et; + for(const auto&line : lines) { + buildTable(line, et); + } + return et; + } + + BoundsMap operator()(const Polygon<double>& polygon) const { + BoundsMap et; + buildPolygonTable(polygon, et); + return et; + } + + BoundsMap operator()(const MultiPolygon<double>& polygons) const { + BoundsMap et; + for(const auto& polygon: polygons) { + buildPolygonTable(polygon, et); + } + return et; + } + + BoundsMap operator()(const mapbox::geometry::geometry_collection<double>&) const { + return {}; + } +}; + +TileCover::Impl::Impl(int32_t z, const Geometry<double>& geom, bool project) + : zoom(z) { + ToFeatureType toFeatureType; + isClosed = apply_visitor(toFeatureType, geom) == FeatureType::Polygon; + + BuildBoundsMap toBoundsMap(z, project); + boundsMap = apply_visitor(toBoundsMap, geom); + if (boundsMap.size() == 0) return; + + //Iniitalize the active edge table, and current row span + currentBounds = boundsMap.begin(); + tileY = 0; + nextRow(); + if (tileXSpans.empty()) return; + tileX = tileXSpans.front().first; +} + +void TileCover::Impl::nextRow() { + // Update AET 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)); + currentBounds++; + } + } + //Scan aet and update currenRange with x_min, x_max pairs + auto xps = util::scan_row(tileY, activeBounds); + if (xps.size() == 0) { + return; + } + + auto x_min = xps[0].xmin; + auto x_max = xps[0].xmax; + int32_t nzRule = xps[0].winding ? 1 : -1; + for (size_t i = 1; i < xps.size(); i++) { + auto xp = xps[i]; + if (!(isClosed && nzRule != 0)) { + if (xp.xmin > x_max && xp.xmax >= x_max) { + tileXSpans.emplace(x_min, x_max); + x_min = xp.xmin; + } + } + nzRule += xp.winding ? 1 : -1; + x_max = std::max(x_min, xp.xmax); + } + tileXSpans.emplace(x_min, x_max); +} + +bool TileCover::Impl::hasNext() const { + return (!tileXSpans.empty() && tileX < tileXSpans.front().second && tileY < (1u << zoom)); +} + +optional<UnwrappedTileID> TileCover::Impl::next() { + if (!hasNext()) return {}; + + const auto x = tileX; + const auto y = tileY; + tileX++; + if (tileX >= tileXSpans.front().second) { + tileXSpans.pop(); + if(tileXSpans.empty()) { + tileY++; + nextRow(); + } + if (!tileXSpans.empty()) { + tileX = tileXSpans.front().first; + } + } + return UnwrappedTileID(zoom, x, y); +} + +} // namespace util +} // namespace mbgl |