From 700180a0fecc030ecb8b72e9f9ce1b4bb798b45c Mon Sep 17 00:00:00 2001 From: Ansis Brammanis Date: Thu, 28 Apr 2016 18:00:39 -0700 Subject: [core] use a GridIndex for queryRenderedFeatures --- src/mbgl/geometry/feature_index.cpp | 42 +++++++------------ src/mbgl/geometry/feature_index.hpp | 33 ++------------- src/mbgl/tile/tile_worker.cpp | 1 - src/mbgl/util/grid_index.cpp | 82 +++++++++++++++++++++++++++++++++++++ src/mbgl/util/grid_index.hpp | 42 +++++++++++++++++++ 5 files changed, 142 insertions(+), 58 deletions(-) create mode 100644 src/mbgl/util/grid_index.cpp create mode 100644 src/mbgl/util/grid_index.hpp (limited to 'src') 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 #include #include +#include #include #include 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::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& vector, const std::string& s) { return std::find(vector.begin(), vector.end(), s) != vector.end(); } @@ -61,8 +52,8 @@ bool vectorsIntersect(const std::vector& 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 matchingBoxes; - tree.query(bgi::intersects(queryBox), std::back_inserter(matchingBoxes)); - std::sort(matchingBoxes.begin(), matchingBoxes.end(), topDown); + std::vector 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::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 +#include #include #include #include -#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 -#include -#include -#include -#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 TreePoint; -typedef bgm::box TreeBox; -typedef std::pair FeatureTreeBox; -typedef bgi::rtree> 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>& result, @@ -89,8 +62,8 @@ class FeatureIndex { const float pixelsToTileUnits) const; std::unique_ptr collisionTile; - std::vector treeBoxes; - FeatureTree tree; + GridIndex grid; + unsigned int sortIndex = 0; std::unordered_map> 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 +#include + +#include + +namespace mbgl { + + +template +GridIndex::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 +void GridIndex::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 +std::vector GridIndex::query(const BBox& queryBBox) const { + std::vector result; + std::unordered_set 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 +int32_t GridIndex::convertToCellCoord(int32_t x) const { + return std::max(0.0, std::min(d - 1.0, std::floor(x * scale) + padding)); +} + +template class GridIndex; +} 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 +#include +#include + +namespace mbgl { + +template +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 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> elements; + std::vector> cells; + +}; + +} -- cgit v1.2.1