diff options
| -rw-r--r-- | include/mbgl/style/expression/within.hpp | 3 | ||||
| -rw-r--r-- | src/mbgl/style/expression/within.cpp | 233 | ||||
| -rw-r--r-- | src/mbgl/util/geometry_within.cpp | 92 | ||||
| -rw-r--r-- | src/mbgl/util/geometry_within.hpp | 20 |
4 files changed, 180 insertions, 168 deletions
diff --git a/include/mbgl/style/expression/within.hpp b/include/mbgl/style/expression/within.hpp index eb23c7d0e0..a8e45f9bf0 100644 --- a/include/mbgl/style/expression/within.hpp +++ b/include/mbgl/style/expression/within.hpp @@ -11,7 +11,7 @@ namespace expression { class Within final : public Expression { public: - explicit Within(GeoJSON geojson, Feature::geometry_type geometries_, const WithinBBox& polygonBBox_); + explicit Within(GeoJSON geojson, Feature::geometry_type geometries_); ~Within() override; @@ -31,7 +31,6 @@ public: private: GeoJSON geoJSONSource; Feature::geometry_type geometries; - WithinBBox polygonBBox; }; } // namespace expression diff --git a/src/mbgl/style/expression/within.cpp b/src/mbgl/style/expression/within.cpp index 49ae8b54a8..0f2f837420 100644 --- a/src/mbgl/style/expression/within.cpp +++ b/src/mbgl/style/expression/within.cpp @@ -9,78 +9,149 @@ #include <mbgl/util/string.hpp> #include <rapidjson/document.h> +#include <mbgl/math/clamp.hpp> namespace mbgl { namespace { -bool pointsWithinPolygons(const mbgl::GeometryTileFeature& feature, - const mbgl::CanonicalTileID& canonical, - const Feature::geometry_type& polygonGeoSet, - const WithinBBox& polyBBox) { - return polygonGeoSet.match( - [&feature, &canonical, &polyBBox](const mapbox::geometry::multi_polygon<double>& polygons) -> bool { - return convertGeometry(feature, canonical) - .match( - [&polygons, &polyBBox](const mapbox::geometry::point<double>& point) -> bool { - return boxWithinBox(calculateBBox(point), polyBBox) && pointWithinPolygons(point, polygons); - }, - [&polygons, &polyBBox](const mapbox::geometry::multi_point<double>& points) -> bool { - return boxWithinBox(calculateBBox(points), polyBBox) && - std::all_of(points.begin(), points.end(), [&polygons](const auto& p) { - return pointWithinPolygons(p, polygons); - }); - }, - [](const auto&) -> bool { return false; }); - }, - [&feature, &canonical, &polyBBox](const mapbox::geometry::polygon<double>& polygon) -> bool { - return convertGeometry(feature, canonical) - .match( - [&polygon, &polyBBox](const mapbox::geometry::point<double>& point) -> bool { - return boxWithinBox(calculateBBox(point), polyBBox) && pointWithinPolygon(point, polygon); - }, - [&polygon, &polyBBox](const mapbox::geometry::multi_point<double>& points) -> bool { - return boxWithinBox(calculateBBox(points), polyBBox) && - std::all_of(points.begin(), points.end(), [&polygon](const auto& p) { - return pointWithinPolygon(p, polygon); - }); - }, - [](const auto&) -> bool { return false; }); - }, - [](const auto&) -> bool { return false; }); +Point<int64_t> latLonToTileCoodinates(const Point<double>& c, const mbgl::CanonicalTileID& canonical) { + Point<int64_t> p; + + const double size = util::EXTENT * std::pow(2, canonical.z); + + auto x = (c.x + 180.0) * size / 360.0; + p.x = (util::clamp<int64_t>(x, std::numeric_limits<int64_t>::min(), std::numeric_limits<int64_t>::max())); + + auto y = (180 - (std::log(std::tan((c.y + 90) * M_PI / 360.0)) * 180 / M_PI)) * size / 360; + p.y = (util::clamp<int64_t>(y, std::numeric_limits<int64_t>::min(), std::numeric_limits<int64_t>::max())); + + return p; +}; + +Polygon<int64_t> getTilePolygon(const Polygon<double>& polygon, + const mbgl::CanonicalTileID& canonical, + WithinBBox& bbox) { + Polygon<int64_t> result; + result.reserve(polygon.size()); + for (const auto& ring : polygon) { + LinearRing<int64_t> temp; + temp.reserve(ring.size()); + for (const auto p : ring) { + const auto coord = latLonToTileCoodinates(p, canonical); + temp.push_back(coord); + updateBBox(bbox, coord); + } + result.push_back(std::move(temp)); + } + return result; +} + +MultiPolygon<int64_t> getTilePolygons(const MultiPolygon<double>& polygons, + const mbgl::CanonicalTileID& canonical, + WithinBBox& bbox) { + MultiPolygon<int64_t> result; + result.reserve(polygons.size()); + for (const auto& pg : polygons) { + result.push_back(getTilePolygon(pg, canonical, bbox)); + } + return result; +} + +MultiPoint<int64_t> getTilePoints(const GeometryCoordinates& points, + const mbgl::CanonicalTileID& canonical, + WithinBBox& bbox) { + const int64_t x0 = util::EXTENT * canonical.x; + const int64_t y0 = util::EXTENT * canonical.y; + MultiPoint<int64_t> results; + results.reserve(points.size()); + for (const auto& p : points) { + auto point = Point<int64_t>(p.x + x0, p.y + y0); + updateBBox(bbox, point); + results.push_back(point); + } + return results; } -bool linesWithinPolygons(const mbgl::GeometryTileFeature& feature, - const mbgl::CanonicalTileID& canonical, - const Feature::geometry_type& polygonGeoSet, - const WithinBBox& polyBBox) { +MultiLineString<int64_t> getTileLines(const GeometryCollection& lines, + const mbgl::CanonicalTileID& canonical, + WithinBBox& bbox) { + const int64_t x0 = util::EXTENT * canonical.x; + const int64_t y0 = util::EXTENT * canonical.y; + MultiLineString<int64_t> results; + results.reserve(bbox.size()); + for (const auto& line : lines) { + LineString<int64_t> lineString; + lineString.reserve(line.size()); + for (const auto& p : line) { + auto point = Point<int64_t>(p.x + x0, p.y + y0); + updateBBox(bbox, point); + lineString.push_back(point); + } + results.push_back(std::move(lineString)); + } + return results; +} + +bool featureWithinPolygons(const GeometryTileFeature& feature, + const CanonicalTileID& canonical, + const Feature::geometry_type& polygonGeoSet) { return polygonGeoSet.match( - [&feature, &canonical, &polyBBox](const MultiPolygon<double>& polygons) -> bool { - return convertGeometry(feature, canonical) - .match( - [&polygons, &polyBBox](const LineString<double>& line) -> bool { - return boxWithinBox(calculateBBox(line), polyBBox) && lineStringWithinPolygons(line, polygons); - }, - [&polygons, &polyBBox](const MultiLineString<double>& lines) -> bool { - return boxWithinBox(calculateBBox(lines), polyBBox) && - std::all_of(lines.begin(), lines.end(), [&polygons](const auto& line) { - return lineStringWithinPolygons(line, polygons); - }); - }, - [](const auto&) -> bool { return false; }); + [&feature, &canonical](const mapbox::geometry::multi_polygon<double>& polys) -> bool { + WithinBBox polyBBox = DefaultBBox; + auto polygons = getTilePolygons(polys, canonical, polyBBox); + + const GeometryCollection& geometries = feature.getGeometries(); + switch (feature.getType()) { + case FeatureType::Point: { + WithinBBox pointBBox = DefaultBBox; + MultiPoint<int64_t> points = getTilePoints(geometries.at(0), canonical, pointBBox); + if (!boxWithinBox(pointBBox, polyBBox)) return false; + + return std::all_of(points.begin(), points.end(), [&polygons](const auto& p) { + return pointWithinPolygons(p, polygons); + }); + } + case FeatureType::LineString: { + WithinBBox lineBBox = DefaultBBox; + MultiLineString<int64_t> multiLineString = getTileLines(geometries, canonical, lineBBox); + + if (!boxWithinBox(lineBBox, polyBBox)) return false; + + return std::all_of(multiLineString.begin(), multiLineString.end(), [&polygons](const auto& line) { + return lineStringWithinPolygons(line, polygons); + }); + } + default: + return false; + }; }, - [&feature, &canonical, &polyBBox](const Polygon<double>& polygon) -> bool { - return convertGeometry(feature, canonical) - .match( - [&polygon, &polyBBox](const LineString<double>& line) -> bool { - return boxWithinBox(calculateBBox(line), polyBBox) && lineStringWithinPolygon(line, polygon); - }, - [&polygon, &polyBBox](const MultiLineString<double>& lines) -> bool { - return boxWithinBox(calculateBBox(lines), polyBBox) && - std::all_of(lines.begin(), lines.end(), [&polygon](const auto& line) { - return lineStringWithinPolygon(line, polygon); - }); - }, - [](const auto&) -> bool { return false; }); + [&feature, &canonical](const mapbox::geometry::polygon<double>& poly) -> bool { + WithinBBox polyBBox = DefaultBBox; + const auto polygon = getTilePolygon(poly, canonical, polyBBox); + + const GeometryCollection& geometries = feature.getGeometries(); + switch (feature.getType()) { + case FeatureType::Point: { + WithinBBox pointBBox = DefaultBBox; + MultiPoint<int64_t> points = getTilePoints(geometries.at(0), canonical, pointBBox); + if (!boxWithinBox(pointBBox, polyBBox)) return false; + + return std::all_of(points.begin(), points.end(), [&polygon](const auto& p) { + return pointWithinPolygon(p, polygon); + }); + } + case FeatureType::LineString: { + WithinBBox lineBBox = DefaultBBox; + MultiLineString<int64_t> multiLineString = getTileLines(geometries, canonical, lineBBox); + if (!boxWithinBox(lineBBox, polyBBox)) return false; + + return std::all_of(multiLineString.begin(), multiLineString.end(), [&polygon](const auto& line) { + return lineStringWithinPolygon(line, polygon); + }); + } + default: + return false; + }; }, [](const auto&) -> bool { return false; }); } @@ -100,16 +171,11 @@ mbgl::optional<mbgl::GeoJSON> parseValue(const mbgl::style::conversion::Converti return nullopt; } -struct PolygonInfo { - PolygonInfo(const Feature::geometry_type& geometry_) : geometry(geometry_), bbox(calculateBBox(geometry)){}; - Feature::geometry_type geometry; - WithinBBox bbox; -}; - -mbgl::optional<PolygonInfo> getPolygonInfo(const Feature& polyFeature, mbgl::style::expression::ParsingContext& ctx) { +mbgl::optional<Feature::geometry_type> getPolygonInfo(const Feature& polyFeature, + mbgl::style::expression::ParsingContext& ctx) { const auto type = apply_visitor(ToFeatureType(), polyFeature.geometry); if (type == FeatureType::Polygon) { - return PolygonInfo(polyFeature.geometry); + return polyFeature.geometry; } ctx.error("'within' expression requires valid geojson source that contains polygon geometry type."); return nullopt; @@ -119,11 +185,8 @@ mbgl::optional<PolygonInfo> getPolygonInfo(const Feature& polyFeature, mbgl::sty namespace style { namespace expression { -Within::Within(GeoJSON geojson, Feature::geometry_type geometries_, const WithinBBox& polygonBBox_) - : Expression(Kind::Within, type::Boolean), - geoJSONSource(std::move(geojson)), - geometries(std::move(geometries_)), - polygonBBox(polygonBBox_) {} +Within::Within(GeoJSON geojson, Feature::geometry_type geometries_) + : Expression(Kind::Within, type::Boolean), geoJSONSource(std::move(geojson)), geometries(std::move(geometries_)) {} Within::~Within() = default; @@ -134,11 +197,9 @@ EvaluationResult Within::evaluate(const EvaluationContext& params) const { return false; } auto geometryType = params.feature->getType(); - // Currently only support Point/Points in Polygon/Polygons - if (geometryType == FeatureType::Point) { - return pointsWithinPolygons(*params.feature, *params.canonical, geometries, polygonBBox); - } else if (geometryType == FeatureType::LineString) { - return linesWithinPolygons(*params.feature, *params.canonical, geometries, polygonBBox); + // Currently only support Point and LineString types in Polygon/Polygons + if (geometryType == FeatureType::Point || geometryType == FeatureType::LineString) { + return featureWithinPolygons(*params.feature, *params.canonical, geometries); } mbgl::Log::Warning(mbgl::Event::General, "within expression currently only support Point/LineString geometry type."); @@ -163,20 +224,20 @@ ParseResult Within::parse(const Convertible& value, ParsingContext& ctx) { return parsedValue->match( [&parsedValue, &ctx](const mapbox::geometry::geometry<double>& geometrySet) { if (auto ret = getPolygonInfo(mbgl::Feature(geometrySet), ctx)) { - return ParseResult(std::make_unique<Within>(*parsedValue, std::move(ret->geometry), ret->bbox)); + return ParseResult(std::make_unique<Within>(*parsedValue, std::move(*ret))); } return ParseResult(); }, [&parsedValue, &ctx](const mapbox::feature::feature<double>& feature) { if (auto ret = getPolygonInfo(mbgl::Feature(feature), ctx)) { - return ParseResult(std::make_unique<Within>(*parsedValue, std::move(ret->geometry), ret->bbox)); + return ParseResult(std::make_unique<Within>(*parsedValue, std::move(*ret))); } return ParseResult(); }, [&parsedValue, &ctx](const mapbox::feature::feature_collection<double>& features) { for (const auto& feature : features) { if (auto ret = getPolygonInfo(mbgl::Feature(feature), ctx)) { - return ParseResult(std::make_unique<Within>(*parsedValue, std::move(ret->geometry), ret->bbox)); + return ParseResult(std::make_unique<Within>(*parsedValue, std::move(*ret))); } } return ParseResult(); @@ -234,7 +295,7 @@ mbgl::Value Within::serialize() const { bool Within::operator==(const Expression& e) const { if (e.getKind() == Kind::Within) { auto rhs = static_cast<const Within*>(&e); - return geoJSONSource == rhs->geoJSONSource && geometries == rhs->geometries && polygonBBox == rhs->polygonBBox; + return geoJSONSource == rhs->geoJSONSource && geometries == rhs->geometries; } return false; } diff --git a/src/mbgl/util/geometry_within.cpp b/src/mbgl/util/geometry_within.cpp index 4a0a5cce11..3c5e26c940 100644 --- a/src/mbgl/util/geometry_within.cpp +++ b/src/mbgl/util/geometry_within.cpp @@ -5,12 +5,14 @@ namespace mbgl { namespace { -bool rayIntersect(const Point<double>& p, const Point<double>& p1, const Point<double>& p2) { + +bool rayIntersect(const Point<int64_t>& p, const Point<int64_t>& p1, const Point<int64_t>& p2) { return ((p1.y > p.y) != (p2.y > p.y)) && (p.x < (p2.x - p1.x) * (p.y - p1.y) / (p2.y - p1.y) + p1.x); } // check if point p in on line segment with end points p1 and p2 -bool onBoundary(const Point<double>& p, const Point<double>& p1, const Point<double>& p2) { + +bool onBoundary(const Point<int64_t>& p, const Point<int64_t>& p1, const Point<int64_t>& p2) { // requirements of point p on line segment: // 1. colinear: cross product of vector p->p1(x1, y1) and vector p->p2(x2, y2) equals to 0 // 2. p is between p1 and p2 @@ -22,20 +24,24 @@ bool onBoundary(const Point<double>& p, const Point<double>& p1, const Point<dou } // a, b are end points for line segment1, c and d are end points for line segment2 -bool lineIntersectLine(const Point<double>& a, const Point<double>& b, const Point<double>& c, const Point<double>& d) { - const auto perp = [](const Point<double>& v1, const Point<double>& v2) { return (v1.x * v2.y - v1.y * v2.x); }; + +bool lineIntersectLine(const Point<int64_t>& a, + const Point<int64_t>& b, + const Point<int64_t>& c, + const Point<int64_t>& d) { + const auto perp = [](const Point<int64_t>& v1, const Point<int64_t>& v2) { return (v1.x * v2.y - v1.y * v2.x); }; // check if two segments are parallel or not // precondition is end point a, b is inside polygon, if line a->b is // parallel to polygon edge c->d, then a->b won't intersect with c->d - auto vectorP = Point<double>(b.x - a.x, b.y - a.y); - auto vectorQ = Point<double>(d.x - c.x, d.y - c.y); + auto vectorP = Point<int64_t>(b.x - a.x, b.y - a.y); + auto vectorQ = Point<int64_t>(d.x - c.x, d.y - c.y); if (perp(vectorQ, vectorP) == 0) return false; // check if p1 and p2 are in different sides of line segment q1->q2 const auto twoSided = - [](const Point<double>& p1, const Point<double>& p2, const Point<double>& q1, const Point<double>& q2) { - double x1, y1, x2, y2, x3, y3; + [](const Point<int64_t>& p1, const Point<int64_t>& p2, const Point<int64_t>& q1, const Point<int64_t>& q2) { + int64_t x1, y1, x2, y2, x3, y3; // q1->p1 (x1, y1), q1->p2 (x2, y2), q1->q2 (x3, y3) x1 = p1.x - q1.x; @@ -55,7 +61,7 @@ bool lineIntersectLine(const Point<double>& a, const Point<double>& b, const Poi return false; } -bool lineIntersectPolygon(const Point<double>& p1, const Point<double>& p2, const Polygon<double>& polygon) { +bool lineIntersectPolygon(const Point<int64_t>& p1, const Point<int64_t>& p2, const Polygon<int64_t>& polygon) { for (auto ring : polygon) { auto length = ring.size(); // loop through every edge of the ring @@ -68,21 +74,16 @@ bool lineIntersectPolygon(const Point<double>& p1, const Point<double>& p2, cons return false; } -void updateBBox(WithinBBox& bbox, const Point<double>& p) { +} // namespace + +void updateBBox(WithinBBox& bbox, const Point<int64_t>& p) { bbox[0] = std::min(p.x, bbox[0]); bbox[1] = std::min(p.y, bbox[1]); bbox[2] = std::max(p.x, bbox[2]); bbox[3] = std::max(p.y, bbox[3]); } -bool isBBoxValid(const WithinBBox& bbox) { - return bbox != DefaultBBox; -} - -} // namespace - bool boxWithinBox(const WithinBBox& bbox1, const WithinBBox& bbox2) { - if (!isBBoxValid(bbox1) || !isBBoxValid(bbox2)) return false; if (bbox1[0] <= bbox2[0]) return false; if (bbox1[2] >= bbox2[2]) return false; if (bbox1[1] <= bbox2[1]) return false; @@ -90,57 +91,8 @@ bool boxWithinBox(const WithinBBox& bbox1, const WithinBBox& bbox2) { return true; } -WithinBBox calculateBBox(const Geometry<double>& geometries) { - WithinBBox result = DefaultBBox; - - return geometries.match( - [&result](const Point<double>& point) { - updateBBox(result, point); - return result; - }, - [&result](const MultiPoint<double>& points) { - for (const auto point : points) { - updateBBox(result, point); - } - return result; - }, - [&result](const LineString<double>& line) { - for (const auto point : line) { - updateBBox(result, point); - } - return result; - }, - [&result](const MultiLineString<double>& lines) { - for (const auto& line : lines) { - for (const auto point : line) { - updateBBox(result, point); - } - } - return result; - }, - [&result](const Polygon<double>& polygon) { - for (const auto& ring : polygon) { - for (const auto point : ring) { - updateBBox(result, point); - } - } - return result; - }, - [&result](const MultiPolygon<double>& polygons) { - for (const auto& polygon : polygons) { - for (const auto& ring : polygon) { - for (const auto point : ring) { - updateBBox(result, point); - } - } - } - return result; - }, - [](const auto&) { return DefaultBBox; }); -} - // ray casting algorithm for detecting if point is in polygon -bool pointWithinPolygon(const Point<double>& point, const Polygon<double>& polygon) { +bool pointWithinPolygon(const Point<int64_t>& point, const Polygon<int64_t>& polygon) { bool within = false; for (const auto& ring : polygon) { const auto length = ring.size(); @@ -155,14 +107,14 @@ bool pointWithinPolygon(const Point<double>& point, const Polygon<double>& polyg return within; } -bool pointWithinPolygons(const Point<double>& point, const MultiPolygon<double>& polygons) { +bool pointWithinPolygons(const Point<int64_t>& point, const MultiPolygon<int64_t>& polygons) { for (const auto& polygon : polygons) { if (pointWithinPolygon(point, polygon)) return true; } return false; } -bool lineStringWithinPolygon(const LineString<double>& line, const Polygon<double>& polygon) { +bool lineStringWithinPolygon(const LineString<int64_t>& line, const Polygon<int64_t>& polygon) { const auto length = line.size(); // First, check if geometry points of line segments are all inside polygon for (std::size_t i = 0; i < length; ++i) { @@ -180,7 +132,7 @@ bool lineStringWithinPolygon(const LineString<double>& line, const Polygon<doubl return true; } -bool lineStringWithinPolygons(const LineString<double>& line, const MultiPolygon<double>& polygons) { +bool lineStringWithinPolygons(const LineString<int64_t>& line, const MultiPolygon<int64_t>& polygons) { for (const auto& polygon : polygons) { if (lineStringWithinPolygon(line, polygon)) return true; } diff --git a/src/mbgl/util/geometry_within.hpp b/src/mbgl/util/geometry_within.hpp index 56f755c7d7..b078783501 100644 --- a/src/mbgl/util/geometry_within.hpp +++ b/src/mbgl/util/geometry_within.hpp @@ -7,23 +7,23 @@ namespace mbgl { // contains minX, minY, maxX, maxY -using WithinBBox = std::array<double, 4>; -const WithinBBox DefaultBBox = WithinBBox{std::numeric_limits<double>::infinity(), - std::numeric_limits<double>::infinity(), - -std::numeric_limits<double>::infinity(), - -std::numeric_limits<double>::infinity()}; +using WithinBBox = std::array<int64_t, 4>; +const WithinBBox DefaultBBox = WithinBBox{std::numeric_limits<int64_t>::max(), + std::numeric_limits<int64_t>::max(), + std::numeric_limits<int64_t>::min(), + std::numeric_limits<int64_t>::min()}; // check if bbox1 is within bbox2 bool boxWithinBox(const WithinBBox& bbox1, const WithinBBox& bbox2); -WithinBBox calculateBBox(const Geometry<double>& geometries); +void updateBBox(WithinBBox& bbox, const Point<int64_t>& p); -bool pointWithinPolygon(const Point<double>& point, const Polygon<double>& polygon); +bool pointWithinPolygon(const Point<int64_t>& point, const Polygon<int64_t>& polygon); -bool pointWithinPolygons(const Point<double>& point, const MultiPolygon<double>& polygons); +bool pointWithinPolygons(const Point<int64_t>& point, const MultiPolygon<int64_t>& polygons); -bool lineStringWithinPolygon(const LineString<double>& lineString, const Polygon<double>& polygon); +bool lineStringWithinPolygon(const LineString<int64_t>& lineString, const Polygon<int64_t>& polygon); -bool lineStringWithinPolygons(const LineString<double>& line, const MultiPolygon<double>& polygons); +bool lineStringWithinPolygons(const LineString<int64_t>& line, const MultiPolygon<int64_t>& polygons); } // namespace mbgl |