GridIndex support for queries fully containing or fully outside of grid

2 files changed, 52 insertions, 0 deletions

diff --git a/src/mbgl/util/grid_index.cpp b/src/mbgl/util/grid_index.cpp
index 1472325676..7f2ed78e5f 100644
--- a/src/mbgl/util/grid_index.cpp
+++ b/src/mbgl/util/grid_index.cpp
@@ -104,9 +104,41 @@ bool GridIndex<T>::hitTest(const BCircle& queryBCircle) const {
 }
 
 template <class T>
+bool GridIndex<T>::noIntersection(const BBox& query) const {
+    return query.max.x < 0 || query.min.x > width || query.max.y < 0 || query.min.y > height;
+}
+
+template <class T>
+bool GridIndex<T>::completeIntersection(const BBox& query) const {
+    return query.min.x <= 0 && query.min.y <= 0 && width <= query.max.x && height <= query.max.y;
+}
+
+template <class T>
+typename GridIndex<T>::BBox GridIndex<T>::convertToBox(const BCircle& circle) const {
+    return BBox{{circle.center.x - circle.radius, circle.center.y - circle.radius},
+                {circle.center.x + circle.radius, circle.center.y + circle.radius}};
+}
+
+template <class T>
 void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&)> resultFn) const {
     std::unordered_set<size_t> seenBoxes;
     std::unordered_set<size_t> seenCircles;
+    
+    if (noIntersection(queryBBox)) {
+        return;
+    } else if (completeIntersection(queryBBox)) {
+        // TODO: std::for_each?
+        for (auto& element : boxElements) {
+            if (resultFn(element.first)) {
+                return;
+            };
+        }
+        for (auto& element : circleElements) {
+            if (resultFn(element.first)) {
+                return;
+            };
+        }
+    }
 
     auto cx1 = convertToXCellCoord(queryBBox.min.x);
     auto cy1 = convertToYCellCoord(queryBBox.min.y);
@@ -155,6 +187,23 @@ void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const
     std::unordered_set<size_t> seenBoxes;
     std::unordered_set<size_t> seenCircles;
 
+    BBox queryBBox = convertToBox(queryBCircle);
+    if (noIntersection(queryBBox)) {
+        return;
+    } else if (completeIntersection(queryBBox)) {
+        // TODO: std::for_each?
+        for (auto& element : boxElements) {
+            if (resultFn(element.first)) {
+                return;
+            };
+        }
+        for (auto& element : circleElements) {
+            if (resultFn(element.first)) {
+                return;
+            };
+        }
+    }
+
     auto cx1 = convertToXCellCoord(queryBCircle.center.x - queryBCircle.radius);
     auto cy1 = convertToYCellCoord(queryBCircle.center.y - queryBCircle.radius);
     auto cx2 = convertToXCellCoord(queryBCircle.center.x + queryBCircle.radius);
diff --git a/src/mbgl/util/grid_index.hpp b/src/mbgl/util/grid_index.hpp
index 9c1b1524e6..20e3dfff68 100644
--- a/src/mbgl/util/grid_index.hpp
+++ b/src/mbgl/util/grid_index.hpp
@@ -74,6 +74,9 @@ public:
     bool empty() const;
 
 private:
+    bool noIntersection(const BBox& query) const;
+    bool completeIntersection(const BBox& query) const;
+    BBox convertToBox(const BCircle& circle) const;
 
     void query(const BBox&, std::function<bool (const T&)>) const;
     void query(const BCircle&, std::function<bool (const T&)>) const;