diff options
-rw-r--r-- | src/mbgl/geometry/feature_index.cpp | 42 | ||||
-rw-r--r-- | src/mbgl/geometry/feature_index.hpp | 33 | ||||
-rw-r--r-- | src/mbgl/tile/tile_worker.cpp | 1 | ||||
-rw-r--r-- | src/mbgl/util/grid_index.cpp | 82 | ||||
-rw-r--r-- | src/mbgl/util/grid_index.hpp | 42 |
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; + +}; + +} |