diff options
author | zmiao <miao.zhao@mapbox.com> | 2020-02-17 17:30:30 +0200 |
---|---|---|
committer | zmiao <miao.zhao@mapbox.com> | 2020-02-21 21:39:48 +0200 |
commit | 0cc042434d04989d8450575075fce2958e57bbc0 (patch) | |
tree | 3b9c5ece1e9aa7a1d2eff79df783e3276f54106b /src | |
parent | 44f9a694c57d94640f070d3c5b0fc4c918798097 (diff) | |
download | qtlocation-mapboxgl-0cc042434d04989d8450575075fce2958e57bbc0.tar.gz |
[core] Add support for "line within polygon"
Diffstat (limited to 'src')
-rw-r--r-- | src/mbgl/style/expression/within.cpp | 201 |
1 files changed, 197 insertions, 4 deletions
diff --git a/src/mbgl/style/expression/within.cpp b/src/mbgl/style/expression/within.cpp index 0df0bd86ce..dd9c280b89 100644 --- a/src/mbgl/style/expression/within.cpp +++ b/src/mbgl/style/expression/within.cpp @@ -4,6 +4,7 @@ #include <mapbox/geometry.hpp> #include <mbgl/style/conversion_impl.hpp> #include <mbgl/tile/geometry_tile_data.hpp> + #include <mbgl/util/logging.hpp> #include <mbgl/util/string.hpp> @@ -34,6 +35,25 @@ public: } }; +void printPolygon(const Polygon<double>& polygon) { + mbgl::Log::Debug(mbgl::Event::General, "-------Print Polygon------"); + for (auto ring : polygon) { + auto length = ring.size(); + mbgl::Log::Debug(mbgl::Event::General, "-------Print New ring with size: %d ------", length); + // loop through every edge of the ring + for (std::size_t i = 0; i < length - 1; ++i) { + mbgl::Log::Debug(mbgl::Event::General, "point [%.15f, %.15f],", ring[i].x, ring[i].y); + } + } +} + +void printLine(const LineString<double>& lineString) { + mbgl::Log::Debug(mbgl::Event::General, "-------Print LineString------"); + for (std::size_t i = 0; i < lineString.size(); ++i) { + mbgl::Log::Debug(mbgl::Event::General, "point [%.15f, %.15f],", lineString[i].x, lineString[i].y); + } +} + bool rayIntersect(const mbgl::Point<double>& p, const mbgl::Point<double>& p1, const mbgl::Point<double>& 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); } @@ -42,9 +62,9 @@ bool rayIntersect(const mbgl::Point<double>& p, const mbgl::Point<double>& p1, c bool pointWithinPolygon(const mbgl::Point<double>& point, const mapbox::geometry::polygon<double>& polygon) { bool within = false; for (auto ring : polygon) { - auto size = ring.size(); + auto length = ring.size(); // loop through every edge of the ring - for (std::size_t i = 0; i < size - 1; ++i) { + for (std::size_t i = 0; i < length - 1; ++i) { if (rayIntersect(point, ring[i], ring[i + 1])) { within = !within; } @@ -60,12 +80,97 @@ bool pointWithinPolygons(const mbgl::Point<double>& point, const mapbox::geometr return false; } +bool lineIntersectLine(const mbgl::Point<double>& p1, + const mbgl::Point<double>& p2, + const mbgl::Point<double>& q1, + const mbgl::Point<double>& q2) { + // precondition is p1, p2 is inside polygon, so p1, p2 is not on line q1->q2 + const auto perp = [](const mbgl::Point<double>& v1, const mbgl::Point<double>& v2) { + return (v1.x * v2.y - v1.y * v2.x); + }; + + // check if p1 and p2 are in different sides of line segment q1->q2 + const auto twoSided = [](const mbgl::Point<double>& p1, + const mbgl::Point<double>& p2, + const mbgl::Point<double>& q1, + const mbgl::Point<double>& q2) { + double x1, y1, x2, y2, x3, y3; + + // q1->p1 (x1, y1), q1->p2 (x2, y2), q1->q2 (x3, y3) + x1 = p1.x - q1.x; + y1 = p1.y - q1.y; + x2 = p2.x - q1.x; + y2 = p2.y - q1.y; + x3 = q2.x - q1.x; + y3 = q2.y - q1.y; + if ((x1 * y3 - x3 * y1) * (x2 * y3 - x3 * y2) < 0) return true; + return false; + }; + auto vectorP = mbgl::Point<double>(p2.x - p1.x, p2.y - p1.y); + auto vectorQ = mbgl::Point<double>(q2.x - q1.x, q2.y - q1.y); + + // check if two segments are parallel or not + if (perp(vectorQ, vectorP) == 0) return false; + + // check if there are intersecting with each other + // p1 and p2 lie in separate side of segment q1->q2 + // q1 and q2 lie in separate side of segment p1->p2 + if (twoSided(p1, p2, q1, q2) && twoSided(q1, q2, p1, p2)) return true; + return false; +} + +bool lineIntersectPolygon(const mbgl::Point<double>& p1, + const mbgl::Point<double>& p2, + const mapbox::geometry::polygon<double>& polygon) { + for (auto ring : polygon) { + auto length = ring.size(); + // loop through every edge of the ring + for (std::size_t i = 0; i < length - 1; ++i) { + if (lineIntersectLine(p1, p2, ring[i], ring[i + 1])) { + // mbgl::Log::Debug(mbgl::Event::General, + // "intersecting with edge from %.15f to %.15f", i, i+ 1); + return true; + } + } + } + return false; +} + +bool lineStringWithinPolygon(const mbgl::LineString<double>& lineString, + const mapbox::geometry::polygon<double>& polygon) { + // First, check if endpoints of line are all inside polygon + for (std::size_t i = 0; i < lineString.size() - 1; ++i) { + if (!pointWithinPolygon(lineString[i], polygon)) { + mbgl::Log::Debug( + mbgl::Event::General, "point %.15f, %.15f is not inside polygon", lineString[i].x, lineString[i].y); + return false; + } + } + + // Second, check if there was line segment intersecting polygon edge + for (std::size_t i = 0; i < lineString.size() - 1; ++i) { + if (lineIntersectPolygon(lineString[i], lineString[i + 1], polygon)) { + mbgl::Log::Debug(mbgl::Event::General, + "---------line [%.15f, %.15f] to [%.15f, %.15f] is not inside polygon", + lineString[i].x, + lineString[i].y, + lineString[i + 1].x, + lineString[i + 1].y); + return false; + } + } + + mbgl::Log::Debug(mbgl::Event::General, "---------line is inside polygon, line point size: %d: ", lineString.size()); + return true; +} + bool pointsWithinPolygons(const mbgl::GeometryTileFeature& feature, const mbgl::CanonicalTileID& canonical, const mbgl::GeoJSON& geoJson) { return geoJson.match( [&feature, &canonical](const mapbox::geometry::geometry<double>& geometrySet) -> bool { mbgl::Feature f(geometrySet); + PolygonFeature polyFeature(f, canonical); auto refinedGeoSet = convertGeometry(polyFeature, canonical); return refinedGeoSet.match( @@ -80,7 +185,9 @@ bool pointsWithinPolygons(const mbgl::GeometryTileFeature& feature, return pointWithinPolygons(p, polygons); }); }, - [](const auto&) -> bool { return false; }); + [](const auto&) -> bool { + return false; + }); }, [&feature, &canonical](const mapbox::geometry::polygon<double>& polygon) -> bool { return convertGeometry(feature, canonical) @@ -100,6 +207,73 @@ bool pointsWithinPolygons(const mbgl::GeometryTileFeature& feature, [](const auto&) -> bool { return false; }); } +bool lineStringWithinPolygons(const mbgl::LineString<double>& line, const MultiPolygon<double>& polygons) { + for (auto polygon : polygons) { + if (lineStringWithinPolygon(line, polygon)) return true; + } + return false; +} + +bool linesWithinPolygons(const mbgl::GeometryTileFeature& feature, + const mbgl::CanonicalTileID& canonical, + const mbgl::GeoJSON& geoJson) { + mbgl::Log::Debug(mbgl::Event::General, "------------------------Canonical ID is-------------------------------"); + mbgl::Log::Debug( + mbgl::Event::General, "----- '%d' / '%d' / '%d'-------------", canonical.z, canonical.x, canonical.y); + + return geoJson.match( + [&feature, &canonical](const mapbox::geometry::geometry<double>& geometrySet) -> bool { + mbgl::Feature f(geometrySet); + PolygonFeature polyFeature(f, CanonicalTileID(0, 0, 0)); + auto refinedGeoSet = convertGeometry(polyFeature, CanonicalTileID(0, 0, 0)); + return refinedGeoSet.match( + [&feature, &canonical](const MultiPolygon<double>& polygons) -> bool { + for (auto polygon : polygons) { + printPolygon(polygon); + } + return convertGeometry(feature, canonical) + .match( + [&polygons](const LineString<double>& line) -> bool { + printLine(line); + return lineStringWithinPolygons(line, polygons); + }, + [&polygons](const MultiLineString<double>& lines) -> bool { + return std::all_of(lines.begin(), lines.end(), [&polygons](const auto& line) { + printLine(line); + return lineStringWithinPolygons(line, polygons); + }); + }, + [](const auto&) -> bool { + return false; + }); + }, + [&feature, &canonical](const Polygon<double>& polygon) -> bool { + printPolygon(polygon); + return convertGeometry(feature, canonical) + .match( + [&polygon](const LineString<double>& line) -> bool { + printLine(line); + return lineStringWithinPolygon(line, polygon); + }, + [&polygon](const MultiLineString<double>& lines) -> bool { + return std::all_of(lines.begin(), lines.end(), [&polygon](const auto& line) { + printLine(line); + return lineStringWithinPolygon(line, polygon); + }); + }, + [](const auto&) -> bool { + return false; + }); + }, + [](const auto&) -> bool { + return false; + }); + }, + [](const auto&) -> bool { + return false; + }); +} + mbgl::optional<mbgl::GeoJSON> parseValue(const mbgl::style::conversion::Convertible& value_, mbgl::style::expression::ParsingContext& ctx) { if (isObject(value_)) { @@ -138,7 +312,10 @@ EvaluationResult Within::evaluate(const EvaluationContext& params) const { auto geometryType = params.feature->getType(); // Currently only support Point/Points in Polygon/Polygons if (geometryType == FeatureType::Point) { - return pointsWithinPolygons(*params.feature, *params.canonical, geoJSONSource); + pointsWithinPolygons(*params.feature, *params.canonical, geoJSONSource); + return true; + } else if (geometryType == FeatureType::LineString) { + return linesWithinPolygons(*params.feature, *params.canonical, geoJSONSource); } mbgl::Log::Warning(mbgl::Event::General, "within expression currently only support 'Point' geometry type"); @@ -197,6 +374,22 @@ mbgl::Value Within::serialize() const { return std::vector<mbgl::Value>{{getOperator(), *fromExpressionValue<mbgl::Value>(serialized)}}; } +bool Within::operator==(const Expression& e) const { + if (e.getKind() == Kind::Within) { + auto rhs = static_cast<const Within*>(&e); + return geoJSONSource == rhs->geoJSONSource; + } + return false; +} + +std::vector<optional<Value>> Within::possibleOutputs() const { + return {{true}, {false}}; +} + +std::string Within::getOperator() const { + return "within"; +} + } // namespace expression } // namespace style } // namespace mbgl |