[core] Add bounding box overlapping check before line within polygon test

4 files changed, 144 insertions, 41 deletions

diff --git a/include/mbgl/style/expression/within.hpp b/include/mbgl/style/expression/within.hpp
index 37e27f4940..2bc59a0596 100644
--- a/include/mbgl/style/expression/within.hpp
+++ b/include/mbgl/style/expression/within.hpp
@@ -2,6 +2,7 @@
 
 #include <mbgl/style/expression/expression.hpp>
 #include <mbgl/util/geojson.hpp>
+#include <mbgl/util/geometry_within.hpp>
 #include <mbgl/util/optional.hpp>
 
 namespace mbgl {
@@ -10,7 +11,7 @@ namespace expression {
 
 class Within final : public Expression {
 public:
-    explicit Within(GeoJSON geojson, Feature::geometry_type geometries_);
+    explicit Within(GeoJSON geojson, Feature::geometry_type geometries_, WithinBBox polygonBBox_);
 
     ~Within() override;
 
@@ -30,6 +31,7 @@ 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 18d24b9250..9039ff2fe4 100644
--- a/src/mbgl/style/expression/within.cpp
+++ b/src/mbgl/style/expression/within.cpp
@@ -5,7 +5,6 @@
 #include <mbgl/style/conversion/json.hpp>
 #include <mbgl/tile/geometry_tile_data.hpp>
 
-#include <mbgl/util/geometry_within.hpp>
 #include <mbgl/util/logging.hpp>
 #include <mbgl/util/string.hpp>
 
@@ -37,31 +36,34 @@ public:
 
 bool pointsWithinPolygons(const mbgl::GeometryTileFeature& feature,
                           const mbgl::CanonicalTileID& canonical,
-                          const Feature::geometry_type& polygonGeoSet) {
+                          const Feature::geometry_type& polygonGeoSet,
+                          const WithinBBox& polyBBox) {
     return polygonGeoSet.match(
-        [&feature, &canonical](const mapbox::geometry::multi_polygon<double>& polygons) -> bool {
+        [&feature, &canonical, &polyBBox](const mapbox::geometry::multi_polygon<double>& polygons) -> bool {
             return convertGeometry(feature, canonical)
                 .match(
-                    [&polygons](const mapbox::geometry::point<double>& point) -> bool {
-                        return pointWithinPolygons(point, polygons);
+                    [&polygons, &polyBBox](const mapbox::geometry::point<double>& point) -> bool {
+                        return boxWithinBox(calculateBBox(point), polyBBox) && pointWithinPolygons(point, polygons);
                     },
-                    [&polygons](const mapbox::geometry::multi_point<double>& points) -> bool {
-                        return std::all_of(points.begin(), points.end(), [&polygons](const auto& p) {
-                            return pointWithinPolygons(p, 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](const mapbox::geometry::polygon<double>& polygon) -> bool {
+        [&feature, &canonical, &polyBBox](const mapbox::geometry::polygon<double>& polygon) -> bool {
             return convertGeometry(feature, canonical)
                 .match(
-                    [&polygon](const mapbox::geometry::point<double>& point) -> bool {
-                        return pointWithinPolygon(point, polygon);
+                    [&polygon, &polyBBox](const mapbox::geometry::point<double>& point) -> bool {
+                        return boxWithinBox(calculateBBox(point), polyBBox) && pointWithinPolygon(point, polygon);
                     },
-                    [&polygon](const mapbox::geometry::multi_point<double>& points) -> bool {
-                        return std::all_of(points.begin(), points.end(), [&polygon](const auto& p) {
-                            return pointWithinPolygon(p, 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; });
         },
@@ -70,29 +72,36 @@ bool pointsWithinPolygons(const mbgl::GeometryTileFeature& feature,
 
 bool linesWithinPolygons(const mbgl::GeometryTileFeature& feature,
                          const mbgl::CanonicalTileID& canonical,
-                         const Feature::geometry_type& polygonGeoSet) {
+                         const Feature::geometry_type& polygonGeoSet,
+                         const WithinBBox& polyBBox) {
     return polygonGeoSet.match(
-        [&feature, &canonical](const MultiPolygon<double>& polygons) -> bool {
+        [&feature, &canonical, &polyBBox](const MultiPolygon<double>& polygons) -> bool {
             return convertGeometry(feature, canonical)
-                .match([&polygons](
-                           const LineString<double>& line) -> bool { return lineStringWithinPolygons(line, polygons); },
-                       [&polygons](const MultiLineString<double>& lines) -> bool {
-                           return std::all_of(lines.begin(), lines.end(), [&polygons](const auto& line) {
-                               return lineStringWithinPolygons(line, polygons);
-                           });
-                       },
-                       [](const auto&) -> bool { return false; });
+                .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 Polygon<double>& polygon) -> bool {
+        [&feature, &canonical, &polyBBox](const Polygon<double>& polygon) -> bool {
             return convertGeometry(feature, canonical)
-                .match([&polygon](
-                           const LineString<double>& line) -> bool { return lineStringWithinPolygon(line, polygon); },
-                       [&polygon](const MultiLineString<double>& lines) -> bool {
-                           return std::all_of(lines.begin(), lines.end(), [&polygon](const auto& line) {
-                               return lineStringWithinPolygon(line, polygon);
-                           });
-                       },
-                       [](const auto&) -> bool { return false; });
+                .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; });
         },
         [](const auto&) -> bool { return false; });
 }
@@ -122,8 +131,11 @@ mbgl::optional<mbgl::GeoJSON> parseValue(const mbgl::style::conversion::Converti
 namespace style {
 namespace expression {
 
-Within::Within(GeoJSON geojson, Feature::geometry_type geometries_)
-    : Expression(Kind::Within, type::Boolean), geoJSONSource(std::move(geojson)), geometries(std::move(geometries_)) {}
+Within::Within(GeoJSON geojson, Feature::geometry_type geometries_, WithinBBox polygonBBox_)
+    : Expression(Kind::Within, type::Boolean),
+      geoJSONSource(std::move(geojson)),
+      geometries(std::move(geometries_)),
+      polygonBBox(polygonBBox_) {}
 
 Within::~Within() = default;
 
@@ -136,9 +148,9 @@ 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, geometries);
+        return pointsWithinPolygons(*params.feature, *params.canonical, geometries, polygonBBox);
     } else if (geometryType == FeatureType::LineString) {
-        return linesWithinPolygons(*params.feature, *params.canonical, geometries);
+        return linesWithinPolygons(*params.feature, *params.canonical, geometries, polygonBBox);
     }
     mbgl::Log::Warning(mbgl::Event::General,
                        "within expression currently only support Point/LineString geometry type.");
@@ -165,7 +177,8 @@ ParseResult Within::parse(const Convertible& value, ParsingContext& ctx) {
                 mbgl::Feature f(geometrySet);
                 PolygonFeature polyFeature(f, CanonicalTileID(0, 0, 0));
                 auto refinedGeoSet = convertGeometry(polyFeature, CanonicalTileID(0, 0, 0));
-                return ParseResult(std::make_unique<Within>(*parsedValue, std::move(refinedGeoSet)));
+                auto bbox = calculateBBox(refinedGeoSet);
+                return ParseResult(std::make_unique<Within>(*parsedValue, std::move(refinedGeoSet), bbox));
             },
             [&ctx](const auto&) {
                 ctx.error("'within' expression requires geojson source that contains valid geometry data.");
diff --git a/src/mbgl/util/geometry_within.cpp b/src/mbgl/util/geometry_within.cpp
index 344e15b5d7..c79952b8f2 100644
--- a/src/mbgl/util/geometry_within.cpp
+++ b/src/mbgl/util/geometry_within.cpp
@@ -1,5 +1,7 @@
 #include <mbgl/util/geometry_within.hpp>
 
+#include <algorithm>
+
 namespace mbgl {
 
 namespace {
@@ -53,8 +55,78 @@ bool lineIntersectPolygon(const Point<double>& p1, const Point<double>& p2, cons
     }
     return false;
 }
+
+void updateBBox(WithinBBox& bbox, const Point<double>& 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;
+    if (bbox1[3] >= bbox2[3]) return false;
+    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 within = false;
diff --git a/src/mbgl/util/geometry_within.hpp b/src/mbgl/util/geometry_within.hpp
index 86658ecc83..56f755c7d7 100644
--- a/src/mbgl/util/geometry_within.hpp
+++ b/src/mbgl/util/geometry_within.hpp
@@ -1,8 +1,23 @@
 #pragma once
+
+#include <array>
+#include <limits>
 #include <mbgl/util/geometry.hpp>
 
 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()};
+
+// check if bbox1 is within bbox2
+bool boxWithinBox(const WithinBBox& bbox1, const WithinBBox& bbox2);
+
+WithinBBox calculateBBox(const Geometry<double>& geometries);
+
 bool pointWithinPolygon(const Point<double>& point, const Polygon<double>& polygon);
 
 bool pointWithinPolygons(const Point<double>& point, const MultiPolygon<double>& polygons);
@@ -10,4 +25,5 @@ bool pointWithinPolygons(const Point<double>& point, const MultiPolygon<double>&
 bool lineStringWithinPolygon(const LineString<double>& lineString, const Polygon<double>& polygon);
 
 bool lineStringWithinPolygons(const LineString<double>& line, const MultiPolygon<double>& polygons);
+
 } // namespace mbgl