[core] use a GridIndex for queryRenderedFeatures

2 files changed, 124 insertions, 0 deletions

diff --git a/src/mbgl/util/grid_index.cpp b/src/mbgl/util/grid_index.cpp
new file mode 100644
index 0000000000..8a2ee90213
--- /dev/null
+++ b/src/mbgl/util/grid_index.cpp
@@ -0,0 +1,82 @@
+#include <mbgl/util/grid_index.hpp>
+#include <mbgl/geometry/feature_index.hpp>
+
+#include <unordered_set>
+
+namespace mbgl {
+
+
+template <class T>
+GridIndex<T>::GridIndex(int32_t extent_, int32_t n_, int32_t padding_) :
+    extent(extent_),
+    n(n_),
+    padding(padding_),
+    d(n + 2 * padding),
+    scale(double(n) / double(extent)),
+    min(-double(padding) / n * extent),
+    max(extent + double(padding) / n * extent)
+    {
+        cells.resize(d * d);
+    };
+
+template <class T>
+void GridIndex<T>::insert(T&& t, BBox&& bbox) {
+    size_t uid = elements.size();
+
+    auto cx1 = convertToCellCoord(bbox.x1);
+    auto cy1 = convertToCellCoord(bbox.y1);
+    auto cx2 = convertToCellCoord(bbox.x2);
+    auto cy2 = convertToCellCoord(bbox.y2);
+
+    for (int32_t x = cx1; x <= cx2; x++) {
+        for (int32_t y = cy1; y <= cy2; y++) {
+            auto cellIndex = d * y + x;
+            cells[cellIndex].push_back(uid);
+        }
+    }
+
+    elements.emplace_back(t, bbox);
+}
+
+template <class T>
+std::vector<T> GridIndex<T>::query(const BBox& queryBBox) const {
+    std::vector<T> result;
+    std::unordered_set<size_t> seenUids;
+
+    auto cx1 = convertToCellCoord(queryBBox.x1);
+    auto cy1 = convertToCellCoord(queryBBox.y1);
+    auto cx2 = convertToCellCoord(queryBBox.x2);
+    auto cy2 = convertToCellCoord(queryBBox.y2);
+
+    for (int32_t x = cx1; x <= cx2; x++) {
+        for (int32_t y = cy1; y <= cy2; y++) {
+            auto cellIndex = d * y + x;
+            for (auto uid : cells[cellIndex]) {
+                if (seenUids.count(uid) == 0) {
+                    seenUids.insert(uid);
+
+                    auto& pair = elements.at(uid);
+                    auto& bbox = pair.second;
+                    if (queryBBox.x1 <= bbox.x2 &&
+                        queryBBox.y1 <= bbox.y2 &&
+                        queryBBox.x2 >= bbox.x1 &&
+                        queryBBox.y2 >= bbox.y1) {
+
+                        result.push_back(pair.first);
+                    }
+                }
+            }
+        }
+    }
+
+    return result;
+}
+
+
+template <class T>
+int32_t GridIndex<T>::convertToCellCoord(int32_t x) const {
+    return std::max(0.0, std::min(d - 1.0, std::floor(x * scale) + padding));
+}
+
+template class GridIndex<IndexedSubfeature>;
+}
diff --git a/src/mbgl/util/grid_index.hpp b/src/mbgl/util/grid_index.hpp
new file mode 100644
index 0000000000..c886e7ff48
--- /dev/null
+++ b/src/mbgl/util/grid_index.hpp
@@ -0,0 +1,42 @@
+#pragma once
+
+#include <cstdint>
+#include <cstddef>
+#include <vector>
+
+namespace mbgl {
+
+template <class T>
+class GridIndex {
+    public:
+
+    GridIndex(int32_t extent_, int32_t n_, int32_t padding_);
+
+    struct BBox {
+        int32_t x1;
+        int32_t y1;
+        int32_t x2;
+        int32_t y2;
+    };
+
+    void insert(T&& t, BBox&& bbox);
+    std::vector<T> query(const BBox& bbox) const;
+
+    private:
+
+    int32_t convertToCellCoord(int32_t x) const;
+
+    const int32_t extent;
+    const int32_t n;
+    const int32_t padding;
+    const int32_t d;
+    const double scale;
+    const int32_t min;
+    const int32_t max;
+
+    std::vector<std::pair<T, BBox>> elements;
+    std::vector<std::vector<size_t>> cells;
+
+};
+
+}