[core] Add support for "line within polygon"

2 files changed, 200 insertions, 13 deletions

diff --git a/include/mbgl/style/expression/within.hpp b/include/mbgl/style/expression/within.hpp
index 7e4050509d..900e84296f 100644
--- a/include/mbgl/style/expression/within.hpp
+++ b/include/mbgl/style/expression/within.hpp
@@ -23,18 +23,12 @@ public:
 
     void eachChild(const std::function<void(const Expression&)>&) const override {}
 
-    bool operator==(const Expression& e) const override {
-        if (e.getKind() == Kind::Within) {
-            auto rhs = static_cast<const Within*>(&e);
-            return geoJSONSource == rhs->geoJSONSource;
-        }
-        return false;
-    }
+    bool operator==(const Expression& e) const override;
 
-    std::vector<optional<Value>> possibleOutputs() const override { return {{true}, {false}}; }
+    std::vector<optional<Value>> possibleOutputs() const override;
 
     mbgl::Value serialize() const override;
-    std::string getOperator() const override { return "within"; }
+    std::string getOperator() const override;
 
 private:
     GeoJSON geoJSONSource;
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