[core] use a GridIndex for queryRenderedFeatures

5 files changed, 142 insertions, 58 deletions

diff --git a/src/mbgl/geometry/feature_index.cpp b/src/mbgl/geometry/feature_index.cpp
index 99bda537de..d6e19c1932 100644
--- a/src/mbgl/geometry/feature_index.cpp
+++ b/src/mbgl/geometry/feature_index.cpp
@@ -7,19 +7,18 @@
 #include <mbgl/text/collision_tile.hpp>
 #include <mbgl/util/rapidjson.hpp>
 #include <rapidjson/writer.h>
+#include <mbgl/util/constants.hpp>
 
 #include <cassert>
 #include <string>
 
 using namespace mbgl;
 
-FeatureIndex::FeatureIndex() {}
+FeatureIndex::FeatureIndex() : grid(util::EXTENT, 16, 0) {}
 
 void FeatureIndex::insert(const GeometryCollection& geometries, std::size_t index,
         const std::string& sourceLayerName, const std::string& bucketName) {
 
-    auto sortIndex = treeBoxes.size();
-
     for (auto& ring : geometries) {
 
         float minX = std::numeric_limits<float>::infinity();
@@ -35,20 +34,12 @@ void FeatureIndex::insert(const GeometryCollection& geometries, std::size_t inde
             maxY = util::max(maxY, y);
         }
 
-        treeBoxes.emplace_back(
-            TreeBox {
-                TreePoint { minX, minY },
-                TreePoint { maxX, maxY }
-            },
-            IndexedSubfeature { index, sourceLayerName, bucketName, sortIndex }
-        );
+        grid.insert(
+                IndexedSubfeature { index, sourceLayerName, bucketName, sortIndex++ },
+                { int32_t(minX), int32_t(minY), int32_t(maxX), int32_t(maxY) });
     }
 }
 
-void FeatureIndex::loadTree() {
-    tree.insert(treeBoxes.begin(), treeBoxes.end());
-}
-
 bool vectorContains(const std::vector<std::string>& vector, const std::string& s) {
     return std::find(vector.begin(), vector.end(), s) != vector.end();
 }
@@ -61,8 +52,8 @@ bool vectorsIntersect(const std::vector<std::string>& vectorA, const std::vector
 }
 
 
-bool topDown(const FeatureTreeBox& a, const FeatureTreeBox& b) {
-    return std::get<1>(a).sortIndex > std::get<1>(b).sortIndex;
+bool topDown(const IndexedSubfeature& a, const IndexedSubfeature& b) {
+    return a.sortIndex > b.sortIndex;
 }
 
 bool topDownSymbols(const IndexedSubfeature& a, const IndexedSubfeature& b) {
@@ -97,19 +88,16 @@ void FeatureIndex::query(
         }
     }
 
-    TreeBox queryBox = {
-        TreePoint { minX - additionalRadius, minY - additionalRadius },
-        TreePoint { maxX + additionalRadius, maxY + additionalRadius }
-    };
-
-    // query circle, line, fill features
-    std::vector<FeatureTreeBox> matchingBoxes;
-    tree.query(bgi::intersects(queryBox), std::back_inserter(matchingBoxes));
-    std::sort(matchingBoxes.begin(), matchingBoxes.end(), topDown);
+    std::vector<IndexedSubfeature> features = grid.query({
+        int(minX - additionalRadius),
+        int(minY - additionalRadius),
+        int(maxX + additionalRadius),
+        int(maxY + additionalRadius)
+    });
 
+    std::sort(features.begin(), features.end(), topDown);
     size_t previousSortIndex = std::numeric_limits<size_t>::max();
-    for (auto& matchingBox : matchingBoxes) {
-        auto& indexedFeature = std::get<1>(matchingBox);
+    for (auto& indexedFeature : features) {
 
         // If this feature is the same as the previous feature, skip it.
         if (indexedFeature.sortIndex == previousSortIndex) continue;
diff --git a/src/mbgl/geometry/feature_index.hpp b/src/mbgl/geometry/feature_index.hpp
index dc64ea9cee..0b520a841a 100644
--- a/src/mbgl/geometry/feature_index.hpp
+++ b/src/mbgl/geometry/feature_index.hpp
@@ -2,30 +2,12 @@
 #define MBGL_GEOMETRY_FEATURE_INDEX
 
 #include <mbgl/tile/geometry_tile.hpp>
+#include <mbgl/util/grid_index.hpp>
 
 #include <vector>
 #include <string>
 #include <unordered_map>
 
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wunused-function"
-#pragma GCC diagnostic ignored "-Wunused-parameter"
-#pragma GCC diagnostic ignored "-Wunused-variable"
-#pragma GCC diagnostic ignored "-Wshadow"
-#ifdef __clang__
-#pragma GCC diagnostic ignored "-Wunknown-pragmas"
-#endif
-#pragma GCC diagnostic ignored "-Wpragmas"
-#pragma GCC diagnostic ignored "-Wdeprecated-register"
-#pragma GCC diagnostic ignored "-Wshorten-64-to-32"
-#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
-#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
-#include <boost/geometry.hpp>
-#include <boost/geometry/geometries/point.hpp>
-#include <boost/geometry/geometries/box.hpp>
-#include <boost/geometry/index/rtree.hpp>
-#pragma GCC diagnostic pop
-
 namespace mbgl {
 
 class Style;
@@ -40,20 +22,11 @@ class IndexedSubfeature {
         size_t sortIndex;
 };
 
-namespace bg = boost::geometry;
-namespace bgm = bg::model;
-namespace bgi = bg::index;
-typedef bgm::point<float, 2, bg::cs::cartesian> TreePoint;
-typedef bgm::box<TreePoint> TreeBox;
-typedef std::pair<TreeBox, IndexedSubfeature> FeatureTreeBox;
-typedef bgi::rtree<FeatureTreeBox, bgi::linear<16, 4>> FeatureTree;
-
 class FeatureIndex {
     public:
         FeatureIndex();
 
         void insert(const GeometryCollection&, std::size_t index, const std::string& sourceLayerName, const std::string& bucketName);
-        void loadTree();
 
         void query(
                 std::unordered_map<std::string, std::vector<std::string>>& result,
@@ -89,8 +62,8 @@ class FeatureIndex {
                 const float pixelsToTileUnits) const;
 
         std::unique_ptr<CollisionTile> collisionTile;
-        std::vector<FeatureTreeBox> treeBoxes;
-        FeatureTree tree;
+        GridIndex<IndexedSubfeature> grid;
+        unsigned int sortIndex = 0;
 
         std::unordered_map<std::string,std::vector<std::string>> bucketLayerIDs;
 
diff --git a/src/mbgl/tile/tile_worker.cpp b/src/mbgl/tile/tile_worker.cpp
index 2a631de7bd..bc1fdb4195 100644
--- a/src/mbgl/tile/tile_worker.cpp
+++ b/src/mbgl/tile/tile_worker.cpp
@@ -95,7 +95,6 @@ TileParseResult TileWorker::prepareResult(const PlacementConfig& config) {
 
     if (result.state == TileData::State::parsed) {
         featureIndex->setCollisionTile(placeLayers(config));
-        featureIndex->loadTree();
         result.featureIndex = std::move(featureIndex);
         result.geometryTile = std::move(geometryTile);
     }
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;
+
+};
+
+}