summaryrefslogtreecommitdiff
path: root/src/mbgl/util
diff options
context:
space:
mode:
Diffstat (limited to 'src/mbgl/util')
-rw-r--r--src/mbgl/util/compression.cpp2
-rw-r--r--src/mbgl/util/i18n.cpp37
-rw-r--r--src/mbgl/util/i18n.hpp2
-rw-r--r--src/mbgl/util/intersection_tests.cpp9
-rw-r--r--src/mbgl/util/intersection_tests.hpp1
-rw-r--r--src/mbgl/util/throttler.cpp36
-rw-r--r--src/mbgl/util/throttler.hpp22
-rw-r--r--src/mbgl/util/tile_cover.cpp104
-rw-r--r--src/mbgl/util/tile_cover.hpp24
-rw-r--r--src/mbgl/util/tile_cover_impl.cpp365
-rw-r--r--src/mbgl/util/tile_cover_impl.hpp90
-rw-r--r--src/mbgl/util/tiny_sdf.cpp2
12 files changed, 605 insertions, 89 deletions
diff --git a/src/mbgl/util/compression.cpp b/src/mbgl/util/compression.cpp
index 30e813cbb8..ee3ebe7cae 100644
--- a/src/mbgl/util/compression.cpp
+++ b/src/mbgl/util/compression.cpp
@@ -1,6 +1,6 @@
#include <mbgl/util/compression.hpp>
-#if defined(__QT__) && defined(_WINDOWS)
+#if defined(__QT__) && defined(_WINDOWS) && !defined(__GNUC__)
#include <QtZlib/zlib.h>
#else
#include <zlib.h>
diff --git a/src/mbgl/util/i18n.cpp b/src/mbgl/util/i18n.cpp
index 1fc13bfb7d..5530796915 100644
--- a/src/mbgl/util/i18n.cpp
+++ b/src/mbgl/util/i18n.cpp
@@ -1,4 +1,5 @@
-#include "i18n.hpp"
+#include <mbgl/util/i18n.hpp>
+#include <mbgl/util/utf.hpp>
#include <algorithm>
#include <map>
@@ -65,7 +66,7 @@ DEFINE_IS_IN_UNICODE_BLOCK(UnifiedCanadianAboriginalSyllabics, 0x1400, 0x167F)
// DEFINE_IS_IN_UNICODE_BLOCK(Hanunoo, 0x1720, 0x173F)
// DEFINE_IS_IN_UNICODE_BLOCK(Buhid, 0x1740, 0x175F)
// DEFINE_IS_IN_UNICODE_BLOCK(Tagbanwa, 0x1760, 0x177F)
-// DEFINE_IS_IN_UNICODE_BLOCK(Khmer, 0x1780, 0x17FF)
+DEFINE_IS_IN_UNICODE_BLOCK(Khmer, 0x1780, 0x17FF)
// DEFINE_IS_IN_UNICODE_BLOCK(Mongolian, 0x1800, 0x18AF)
DEFINE_IS_IN_UNICODE_BLOCK(UnifiedCanadianAboriginalSyllabicsExtended, 0x18B0, 0x18FF)
// DEFINE_IS_IN_UNICODE_BLOCK(Limbu, 0x1900, 0x194F)
@@ -581,6 +582,38 @@ std::u16string verticalizePunctuation(const std::u16string& input) {
char16_t verticalizePunctuation(char16_t chr) {
return verticalPunctuation.count(chr) ? verticalPunctuation.at(chr) : 0;
}
+
+bool charInSupportedScript(char16_t chr) {
+ // This is a rough heuristic: whether we "can render" a script
+ // actually depends on the properties of the font being used
+ // and whether differences from the ideal rendering are considered
+ // semantically significant.
+
+ // Even in Latin script, we "can't render" combinations such as the fi
+ // ligature, but we don't consider that semantically significant.n false;
+ if ((chr >= 0x0900 && chr <= 0x0DFF) ||
+ // Main blocks for Indic scripts and Sinhala
+ (chr >= 0x0F00 && chr <= 0x109F) ||
+ // Main blocks for Tibetan and Myanmar
+ isInKhmer(chr)) {
+ // These blocks cover common scripts that require
+ // complex text shaping, based on unicode script metadata:
+ // http://www.unicode.org/repos/cldr/trunk/common/properties/scriptMetadata.txt
+ // where "Web Rank <= 32" "Shaping Required = YES"
+ return false;
+ }
+ return true;
+}
+
+bool isStringInSupportedScript(const std::string& input) {
+ auto u16string = util::utf8_to_utf16::convert(input);
+ for (char16_t chr : u16string) {
+ if (!charInSupportedScript(chr)) {
+ return false;
+ }
+ }
+ return true;
+}
} // namespace i18n
} // namespace util
diff --git a/src/mbgl/util/i18n.hpp b/src/mbgl/util/i18n.hpp
index b3960c743c..a74215a134 100644
--- a/src/mbgl/util/i18n.hpp
+++ b/src/mbgl/util/i18n.hpp
@@ -72,6 +72,8 @@ std::u16string verticalizePunctuation(const std::u16string& input);
@return The character’s specialized vertical form; 0 if not applicable. */
char16_t verticalizePunctuation(char16_t chr);
+
+bool isStringInSupportedScript(const std::string& input);
} // namespace i18n
} // namespace util
diff --git a/src/mbgl/util/intersection_tests.cpp b/src/mbgl/util/intersection_tests.cpp
index e6ce245c0e..780fce98f9 100644
--- a/src/mbgl/util/intersection_tests.cpp
+++ b/src/mbgl/util/intersection_tests.cpp
@@ -82,11 +82,16 @@ bool lineIntersectsBufferedLine(const GeometryCoordinates& lineA, const Geometry
return false;
}
+bool polygonIntersectsBufferedPoint(const GeometryCoordinates& polygon, const GeometryCoordinate& point, float radius) {
+ if (polygonContainsPoint(polygon, point)) return true;
+ if (pointIntersectsBufferedLine(point, polygon, radius)) return true;
+ return false;
+}
+
bool polygonIntersectsBufferedMultiPoint(const GeometryCoordinates& polygon, const GeometryCollection& rings, float radius) {
for (auto& ring : rings) {
for (auto& point : ring) {
- if (polygonContainsPoint(polygon, point)) return true;
- if (pointIntersectsBufferedLine(point, polygon, radius)) return true;
+ if (polygonIntersectsBufferedPoint(polygon, point, radius)) return true;
}
}
return false;
diff --git a/src/mbgl/util/intersection_tests.hpp b/src/mbgl/util/intersection_tests.hpp
index 5bcb29c767..c105fe4dd0 100644
--- a/src/mbgl/util/intersection_tests.hpp
+++ b/src/mbgl/util/intersection_tests.hpp
@@ -9,6 +9,7 @@ bool polygonIntersectsBufferedMultiPoint(const GeometryCoordinates&, const Geome
bool polygonIntersectsBufferedMultiLine(const GeometryCoordinates&, const GeometryCollection&, float radius);
bool polygonIntersectsPolygon(const GeometryCoordinates&, const GeometryCoordinates&);
bool polygonIntersectsMultiPolygon(const GeometryCoordinates&, const GeometryCollection&);
+bool polygonIntersectsBufferedPoint(const GeometryCoordinates& polygon, const GeometryCoordinate& point, float radius);
} // namespace util
} // namespace mbgl
diff --git a/src/mbgl/util/throttler.cpp b/src/mbgl/util/throttler.cpp
deleted file mode 100644
index 910810ce2f..0000000000
--- a/src/mbgl/util/throttler.cpp
+++ /dev/null
@@ -1,36 +0,0 @@
-#include <mbgl/util/throttler.hpp>
-
-namespace mbgl {
-namespace util {
-
-Throttler::Throttler(Duration frequency_, std::function<void()>&& function_)
- : frequency(frequency_)
- , function(std::move(function_))
- , pendingInvocation(false)
- , lastInvocation(TimePoint::min())
-{}
-
-void Throttler::invoke() {
- if (pendingInvocation) {
- return;
- }
-
- Duration timeToNextInvocation = lastInvocation == TimePoint::min()
- ? Duration::zero()
- : (lastInvocation + frequency) - Clock::now();
-
- if (timeToNextInvocation <= Duration::zero()) {
- lastInvocation = Clock::now();
- function();
- } else {
- pendingInvocation = true;
- timer.start(timeToNextInvocation, Duration::zero(), [this]{
- pendingInvocation = false;
- lastInvocation = Clock::now();
- function();
- });
- }
-}
-
-} // namespace util
-} // namespace mbgl
diff --git a/src/mbgl/util/throttler.hpp b/src/mbgl/util/throttler.hpp
deleted file mode 100644
index 175de7ccaf..0000000000
--- a/src/mbgl/util/throttler.hpp
+++ /dev/null
@@ -1,22 +0,0 @@
-#include <mbgl/util/chrono.hpp>
-#include <mbgl/util/timer.hpp>
-
-namespace mbgl {
-namespace util {
-
-class Throttler {
-public:
- Throttler(Duration frequency, std::function<void()>&& function);
-
- void invoke();
-private:
- Duration frequency;
- std::function<void()> function;
-
- Timer timer;
- bool pendingInvocation;
- TimePoint lastInvocation;
-};
-
-} // namespace util
-} // namespace mbgl
diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index 39b562d811..488e6b88ce 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -2,13 +2,18 @@
#include <mbgl/util/constants.hpp>
#include <mbgl/util/interpolate.hpp>
#include <mbgl/map/transform_state.hpp>
+#include <mbgl/util/tile_cover_impl.hpp>
+#include <mbgl/util/tile_coordinate.hpp>
#include <functional>
+#include <list>
namespace mbgl {
namespace {
+using ScanLine = const std::function<void(int32_t x0, int32_t x1, int32_t y)>;
+
// Taken from polymaps src/Layer.js
// https://github.com/simplegeo/polymaps/blob/master/src/Layer.js#L333-L383
struct edge {
@@ -27,8 +32,6 @@ struct edge {
}
};
-using ScanLine = const std::function<void(int32_t x0, int32_t x1, int32_t y)>;
-
// scan-line conversion
static void scanSpans(edge e0, edge e1, int32_t ymin, int32_t ymax, ScanLine scanLine) {
double y0 = ::fmax(ymin, std::floor(e1.y0));
@@ -147,11 +150,11 @@ std::vector<UnwrappedTileID> tileCover(const LatLngBounds& bounds_, int32_t z) {
{ std::min(bounds_.north(), util::LATITUDE_MAX), bounds_.east() });
return tileCover(
- TileCoordinate::fromLatLng(z, bounds.northwest()).p,
- TileCoordinate::fromLatLng(z, bounds.northeast()).p,
- TileCoordinate::fromLatLng(z, bounds.southeast()).p,
- TileCoordinate::fromLatLng(z, bounds.southwest()).p,
- TileCoordinate::fromLatLng(z, bounds.center()).p,
+ Projection::project(bounds.northwest(), z),
+ Projection::project(bounds.northeast(), z),
+ Projection::project(bounds.southeast(), z),
+ Projection::project(bounds.southwest(), z),
+ Projection::project(bounds.center(), z),
z);
}
@@ -169,25 +172,80 @@ std::vector<UnwrappedTileID> tileCover(const TransformState& state, int32_t z) {
z);
}
+std::vector<UnwrappedTileID> tileCover(const Geometry<double>& geometry, int32_t z) {
+ std::vector<UnwrappedTileID> result;
+ TileCover tc(geometry, z, true);
+ while (tc.hasNext()) {
+ result.push_back(*tc.next());
+ };
+
+ return result;
+}
+
// Taken from https://github.com/mapbox/sphericalmercator#xyzbbox-zoom-tms_style-srs
// Computes the projected tiles for the lower left and upper right points of the bounds
// and uses that to compute the tile cover count
-uint64_t tileCount(const LatLngBounds& bounds, uint8_t zoom, uint16_t tileSize_){
-
- auto sw = Projection::project(bounds.southwest().wrapped(), zoom, tileSize_);
- auto ne = Projection::project(bounds.northeast().wrapped(), zoom, tileSize_);
-
- auto x1 = floor(sw.x/ tileSize_);
- auto x2 = floor((ne.x - 1) / tileSize_);
- auto y1 = floor(sw.y/ tileSize_);
- auto y2 = floor((ne.y - 1) / tileSize_);
-
- auto minX = ::fmax(std::min(x1, x2), 0);
- auto maxX = std::max(x1, x2);
- auto minY = (std::pow(2, zoom) - 1) - std::max(y1, y2);
- auto maxY = (std::pow(2, zoom) - 1) - ::fmax(std::min(y1, y2), 0);
-
- return (maxX - minX + 1) * (maxY - minY + 1);
+uint64_t tileCount(const LatLngBounds& bounds, uint8_t zoom){
+ if (zoom == 0) {
+ return 1;
+ }
+ auto sw = Projection::project(bounds.southwest(), zoom);
+ auto ne = Projection::project(bounds.northeast(), zoom);
+ auto maxTile = std::pow(2.0, zoom);
+ auto x1 = floor(sw.x);
+ auto x2 = ceil(ne.x) - 1;
+ auto y1 = util::clamp(floor(sw.y), 0.0, maxTile - 1);
+ auto y2 = util::clamp(floor(ne.y), 0.0, maxTile - 1);
+
+ auto dx = x1 > x2 ? (maxTile - x1) + x2 : x2 - x1;
+ auto dy = y1 - y2;
+ return (dx + 1) * (dy + 1);
+}
+
+uint64_t tileCount(const Geometry<double>& geometry, uint8_t z) {
+ uint64_t tileCount = 0;
+
+ TileCover tc(geometry, z, true);
+ while (tc.next()) {
+ tileCount++;
+ };
+ return tileCount;
+}
+
+TileCover::TileCover(const LatLngBounds&bounds_, int32_t z) {
+ LatLngBounds bounds = LatLngBounds::hull(
+ { std::max(bounds_.south(), -util::LATITUDE_MAX), bounds_.west() },
+ { std::min(bounds_.north(), util::LATITUDE_MAX), bounds_.east() });
+
+ if (bounds.isEmpty() ||
+ bounds.south() > util::LATITUDE_MAX ||
+ bounds.north() < -util::LATITUDE_MAX) {
+ bounds = LatLngBounds::world();
+ }
+
+ auto sw = Projection::project(bounds.southwest(), z);
+ auto ne = Projection::project(bounds.northeast(), z);
+ auto se = Projection::project(bounds.southeast(), z);
+ auto nw = Projection::project(bounds.northwest(), z);
+
+ Polygon<double> p({ {sw, nw, ne, se, sw} });
+ impl = std::make_unique<TileCover::Impl>(z, p, false);
+}
+
+TileCover::TileCover(const Geometry<double>& geom, int32_t z, bool project/* = true*/)
+ : impl( std::make_unique<TileCover::Impl>(z, geom, project)) {
+}
+
+TileCover::~TileCover() {
+
+}
+
+optional<UnwrappedTileID> TileCover::next() {
+ return impl->next();
+}
+
+bool TileCover::hasNext() {
+ return impl->hasNext();
}
} // namespace util
diff --git a/src/mbgl/util/tile_cover.hpp b/src/mbgl/util/tile_cover.hpp
index b2098b59b8..c953d764d2 100644
--- a/src/mbgl/util/tile_cover.hpp
+++ b/src/mbgl/util/tile_cover.hpp
@@ -2,9 +2,11 @@
#include <mbgl/tile/tile_id.hpp>
#include <mbgl/style/types.hpp>
-#include <mbgl/util/tile_coordinate.hpp>
+#include <mbgl/util/geometry.hpp>
+#include <mbgl/util/optional.hpp>
#include <vector>
+#include <memory>
namespace mbgl {
@@ -13,13 +15,31 @@ class LatLngBounds;
namespace util {
+// Helper class to stream tile-cover results per row
+class TileCover {
+public:
+ TileCover(const LatLngBounds&, int32_t z);
+ // When project == true, projects the geometry points to tile coordinates
+ TileCover(const Geometry<double>&, int32_t z, bool project = true);
+ ~TileCover();
+
+ optional<UnwrappedTileID> next();
+ bool hasNext();
+
+private:
+ class Impl;
+ std::unique_ptr<Impl> impl;
+};
+
int32_t coveringZoomLevel(double z, style::SourceType type, uint16_t tileSize);
std::vector<UnwrappedTileID> tileCover(const TransformState&, int32_t z);
std::vector<UnwrappedTileID> tileCover(const LatLngBounds&, int32_t z);
+std::vector<UnwrappedTileID> tileCover(const Geometry<double>&, int32_t z);
// Compute only the count of tiles needed for tileCover
-uint64_t tileCount(const LatLngBounds&, uint8_t z, uint16_t tileSize);
+uint64_t tileCount(const LatLngBounds&, uint8_t z);
+uint64_t tileCount(const Geometry<double>&, uint8_t z);
} // namespace util
} // namespace mbgl
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
diff --git a/src/mbgl/util/tile_cover_impl.hpp b/src/mbgl/util/tile_cover_impl.hpp
new file mode 100644
index 0000000000..7c16718984
--- /dev/null
+++ b/src/mbgl/util/tile_cover_impl.hpp
@@ -0,0 +1,90 @@
+#pragma once
+
+#include <mbgl/util/tile_cover.hpp>
+#include <mbgl/util/geometry.hpp>
+#include <mbgl/util/optional.hpp>
+
+#include <vector>
+#include <map>
+#include <queue>
+
+namespace mbgl {
+
+class TransformState;
+class LatLngBounds;
+
+namespace util {
+
+struct Bound;
+
+using Bounds = std::vector<Bound>;
+using BoundsMap = std::map<uint32_t, Bounds>;
+
+// A chain of points from a local minimum to a local maximum. `winding` indicates
+// the direction of the original geometry.
+struct Bound {
+ std::vector<Point<double>> points;
+ size_t currentPoint = 0;
+ bool winding = false;
+
+ Bound() = default;
+ Bound(const Bound& rhs) {
+ points = rhs.points;
+ currentPoint = rhs.currentPoint;
+ winding = rhs.winding;
+ }
+ Bound& operator=(Bound&& rhs) {
+ points = std::move(rhs.points);
+ currentPoint = rhs.currentPoint;
+ winding = rhs.winding;
+ return *this;
+ }
+
+ // Compute the interpolated x coordinate at y for the current edge
+ double interpolate(uint32_t y) {
+ const auto& p0 = points[currentPoint];
+ const auto& p1 = points[currentPoint + 1];
+
+ const auto dx = p1.x - p0.x;
+ const auto dy = p1.y - p0.y;
+ auto x = p0.x;
+ if (dx == 0) {
+ return x;
+ } else if (dy == 0){
+ return y <= p0.y ? p0.x : p1.x;
+ }
+ if (y < p0.y) return x;
+ if (y > p1.y) return p1.x;
+ x = (dx / dy) * (y - p0.y) + p0.x;
+ return x;
+ }
+};
+
+class TileCover::Impl {
+public:
+ Impl(int32_t z, const Geometry<double>& geom, bool project = true);
+ ~Impl() = default;
+
+ optional<UnwrappedTileID> next();
+ bool hasNext() const;
+
+private:
+ using TileSpans = std::queue<std::pair<int32_t, int32_t>>;
+
+ void nextRow();
+
+ const int32_t zoom;
+ bool isClosed;
+
+ BoundsMap boundsMap;
+ BoundsMap::iterator currentBounds;
+ // List of bounds that begin at or before `tileY`
+ Bounds activeBounds;
+
+ TileSpans tileXSpans;
+ uint32_t tileY;
+ int32_t tileX;
+};
+
+} // namespace util
+} // namespace mbgl
diff --git a/src/mbgl/util/tiny_sdf.cpp b/src/mbgl/util/tiny_sdf.cpp
index 60839357d5..6edcd83bc2 100644
--- a/src/mbgl/util/tiny_sdf.cpp
+++ b/src/mbgl/util/tiny_sdf.cpp
@@ -95,7 +95,7 @@ AlphaImage transformRasterToSDF(const AlphaImage& rasterInput, double radius, do
for (uint32_t i = 0; i < size; i++) {
double distance = gridOuter[i] - gridInner[i];
- sdf.data[i] = std::max(0l, std::min(255l, std::lround(255.0 - 255.0 * (distance / radius + cutoff))));
+ sdf.data[i] = std::max(0l, std::min(255l, ::lround(255.0 - 255.0 * (distance / radius + cutoff))));
}
return sdf;
View Lorry Controller Status