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

1 files changed, 53 insertions, 40 deletions

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.");