summaryrefslogtreecommitdiff
path: root/src/mbgl/util
diff options
context:
space:
mode:
authorAnsis Brammanis <brammanis@gmail.com>2016-04-28 18:00:39 -0700
committerJohn Firebaugh <john.firebaugh@gmail.com>2016-04-29 12:00:24 -0700
commit700180a0fecc030ecb8b72e9f9ce1b4bb798b45c (patch)
treec3a3f75628d29596ed21d190a7a07cbb3e06ccad /src/mbgl/util
parent61d14089e0dd742719328fd74c693bcae6274a4b (diff)
downloadqtlocation-mapboxgl-700180a0fecc030ecb8b72e9f9ce1b4bb798b45c.tar.gz
[core] use a GridIndex for queryRenderedFeatures
Diffstat (limited to 'src/mbgl/util')
-rw-r--r--src/mbgl/util/grid_index.cpp82
-rw-r--r--src/mbgl/util/grid_index.hpp42
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;
+
+};
+
+}