diff options
author | Chris Loer <chris.loer@gmail.com> | 2017-10-23 16:21:35 -0700 |
---|---|---|
committer | Chris Loer <chris.loer@mapbox.com> | 2017-10-24 13:24:22 -0700 |
commit | 64230853645d0d914a3dd9faa40d1d7574a026a8 (patch) | |
tree | 3150eac8be69721d1f26cfd163766e9708f1f80c | |
parent | 95860dd13360de44c0248ce0bd628a29099d1af6 (diff) | |
download | qtlocation-mapboxgl-64230853645d0d914a3dd9faa40d1d7574a026a8.tar.gz |
Initial implementation: add support for circle geometries to GridIndex.
Modify FeatureIndex to use new interface.
-rw-r--r-- | src/mbgl/geometry/feature_index.cpp | 2 | ||||
-rw-r--r-- | src/mbgl/util/grid_index.cpp | 236 | ||||
-rw-r--r-- | src/mbgl/util/grid_index.hpp | 90 |
3 files changed, 279 insertions, 49 deletions
diff --git a/src/mbgl/geometry/feature_index.cpp b/src/mbgl/geometry/feature_index.cpp index 1adb933e44..f7dbbfb8b3 100644 --- a/src/mbgl/geometry/feature_index.cpp +++ b/src/mbgl/geometry/feature_index.cpp @@ -18,7 +18,7 @@ namespace mbgl { FeatureIndex::FeatureIndex() - : grid(util::EXTENT, 16, 0) { + : grid(util::EXTENT, util::EXTENT, util::EXTENT >> 5) { } void FeatureIndex::insert(const GeometryCollection& geometries, diff --git a/src/mbgl/util/grid_index.cpp b/src/mbgl/util/grid_index.cpp index b3afd3fdc8..351c5e5aea 100644 --- a/src/mbgl/util/grid_index.cpp +++ b/src/mbgl/util/grid_index.cpp @@ -3,83 +3,249 @@ #include <mbgl/math/minmax.hpp> #include <unordered_set> +#include <cmath> 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) +GridIndex<T>::GridIndex(int32_t width_, int32_t height_, int32_t cellSize_) : + width(width_), + height(height_), + xCellCount(std::ceil(float(width_) / cellSize_)), + yCellCount(std::ceil(float(height_) / cellSize_)), + xScale(float(xCellCount) / width_), + yScale(float(yCellCount) / height_) { - cells.resize(d * d); + boxCells.resize(xCellCount * yCellCount); + circleCells.resize(xCellCount * yCellCount); } template <class T> void GridIndex<T>::insert(T&& t, const BBox& bbox) { - size_t uid = elements.size(); + size_t uid = boxElements.size(); - auto cx1 = convertToCellCoord(bbox.min.x); - auto cy1 = convertToCellCoord(bbox.min.y); - auto cx2 = convertToCellCoord(bbox.max.x); - auto cy2 = convertToCellCoord(bbox.max.y); + auto cx1 = convertToXCellCoord(bbox.min.x); + auto cy1 = convertToYCellCoord(bbox.min.y); + auto cx2 = convertToXCellCoord(bbox.max.x); + auto cy2 = convertToYCellCoord(bbox.max.y); int32_t x, y, cellIndex; for (x = cx1; x <= cx2; ++x) { for (y = cy1; y <= cy2; ++y) { - cellIndex = d * y + x; - cells[cellIndex].push_back(uid); + cellIndex = xCellCount * y + x; + boxCells[cellIndex].push_back(uid); } } - elements.emplace_back(t, bbox); + boxElements.emplace_back(t, bbox); +} + +template <class T> +void GridIndex<T>::insert(T&& t, const BCircle& bcircle) { + size_t uid = circleElements.size(); + + auto cx1 = convertToXCellCoord(bcircle.center.x - bcircle.radius); + auto cy1 = convertToYCellCoord(bcircle.center.y - bcircle.radius); + auto cx2 = convertToXCellCoord(bcircle.center.x + bcircle.radius); + auto cy2 = convertToYCellCoord(bcircle.center.y + bcircle.radius); + + int32_t x, y, cellIndex; + for (x = cx1; x <= cx2; ++x) { + for (y = cy1; y <= cy2; ++y) { + cellIndex = xCellCount * y + x; + circleCells[cellIndex].push_back(uid); + } + } + + circleElements.emplace_back(t, bcircle); } template <class T> std::vector<T> GridIndex<T>::query(const BBox& queryBBox) const { std::vector<T> result; - std::unordered_set<size_t> seenUids; + query(queryBBox, [&](const T& t) -> bool { + result.push_back(t); + return false; + }); + return result; +} + +// TODO: templatize this on geometry type +template <class T> +std::vector<T> GridIndex<T>::query(const BCircle& queryBCircle) const { + std::vector<T> result; + query(queryBCircle, [&](const T& t) -> bool { + result.push_back(t); + return false; + }); + return result; +} + +template <class T> +bool GridIndex<T>::hitTest(const BBox& queryBBox) const { + bool hit = false; + query(queryBBox, [&](const T&) -> bool { + hit = true; + return true; + }); + return hit; +} + +// TODO: templatize this on geometry type +template <class T> +bool GridIndex<T>::hitTest(const BCircle& queryBCircle) const { + bool hit = false; + query(queryBCircle, [&](const T&) -> bool { + hit = true; + return true; + }); + return hit; +} - auto cx1 = convertToCellCoord(queryBBox.min.x); - auto cy1 = convertToCellCoord(queryBBox.min.y); - auto cx2 = convertToCellCoord(queryBBox.max.x); - auto cy2 = convertToCellCoord(queryBBox.max.y); +template <class T> +void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&)> resultFn) const { + std::unordered_set<size_t> seenBoxes; + std::unordered_set<size_t> seenCircles; + + auto cx1 = convertToXCellCoord(queryBBox.min.x); + auto cy1 = convertToYCellCoord(queryBBox.min.y); + auto cx2 = convertToXCellCoord(queryBBox.max.x); + auto cy2 = convertToYCellCoord(queryBBox.max.y); int32_t x, y, cellIndex; for (x = cx1; x <= cx2; ++x) { for (y = cy1; y <= cy2; ++y) { - cellIndex = d * y + x; - for (auto uid : cells[cellIndex]) { - if (seenUids.count(uid) == 0) { - seenUids.insert(uid); + cellIndex = xCellCount * y + x; + // Look up other boxes + for (auto uid : boxCells[cellIndex]) { + if (seenBoxes.count(uid) == 0) { + seenBoxes.insert(uid); - auto& pair = elements.at(uid); + auto& pair = boxElements.at(uid); auto& bbox = pair.second; - if (queryBBox.min.x <= bbox.max.x && - queryBBox.min.y <= bbox.max.y && - queryBBox.max.x >= bbox.min.x && - queryBBox.max.y >= bbox.min.y) { + if (boxesCollide(queryBBox, bbox)) { + if (resultFn(pair.first)) { + return; + } + } + } + } + + // Look up circles + for (auto uid : circleCells[cellIndex]) { + if (seenCircles.count(uid) == 0) { + seenCircles.insert(uid); + + auto& pair = circleElements.at(uid); + auto& bcircle = pair.second; + if (circleAndBoxCollide(bcircle, queryBBox)) { + if (resultFn(pair.first)) { + return; + } + } + } + } + } + } +} + +template <class T> +void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const T&)> resultFn) const { + std::unordered_set<size_t> seenBoxes; + std::unordered_set<size_t> seenCircles; + + auto cx1 = convertToXCellCoord(queryBCircle.center.x - queryBCircle.radius); + auto cy1 = convertToYCellCoord(queryBCircle.center.y - queryBCircle.radius); + auto cx2 = convertToXCellCoord(queryBCircle.center.x + queryBCircle.radius); + auto cy2 = convertToYCellCoord(queryBCircle.center.y + queryBCircle.radius); + + int32_t x, y, cellIndex; + for (x = cx1; x <= cx2; ++x) { + for (y = cy1; y <= cy2; ++y) { + cellIndex = xCellCount * y + x; + // Look up boxes + for (auto uid : boxCells[cellIndex]) { + if (seenBoxes.count(uid) == 0) { + seenBoxes.insert(uid); - result.push_back(pair.first); + auto& pair = boxElements.at(uid); + auto& bbox = pair.second; + if (circleAndBoxCollide(queryBCircle, bbox)) { + if (resultFn(pair.first)) { + return; + } + } + } + } + + // Look up other circles + for (auto uid : circleCells[cellIndex]) { + if (seenCircles.count(uid) == 0) { + seenCircles.insert(uid); + + auto& pair = circleElements.at(uid); + auto& bcircle = pair.second; + if (circlesCollide(queryBCircle, bcircle)) { + if (resultFn(pair.first)) { + return; + } } } } } } +} - return result; +template <class T> +int32_t GridIndex<T>::convertToXCellCoord(int32_t x) const { + return util::max(0.0, util::min(xCellCount - 1.0, std::floor(x * xScale))); +} + +template <class T> +int32_t GridIndex<T>::convertToYCellCoord(int32_t y) const { + return util::max(0.0, util::min(yCellCount - 1.0, std::floor(y * yScale))); } +template <class T> +bool GridIndex<T>::boxesCollide(const BBox& first, const BBox& second) const { + return first.min.x <= second.max.x && + first.min.y <= second.max.y && + first.max.x >= second.min.x && + first.max.y >= second.min.y; +} + +template <class T> +bool GridIndex<T>::circlesCollide(const BCircle& first, const BCircle& second) const { + auto dx = second.center.x - first.center.x; + auto dy = second.center.y - first.center.y; + auto bothRadii = first.radius + second.radius; + return (bothRadii * bothRadii) > (dx * dx + dy * dy); +} template <class T> -int32_t GridIndex<T>::convertToCellCoord(int32_t x) const { - return util::max(0.0, util::min(d - 1.0, std::floor(x * scale) + padding)); +bool GridIndex<T>::circleAndBoxCollide(const BCircle& circle, const BBox& box) const { + auto halfRectWidth = (box.max.x - box.min.x) / 2; + auto distX = std::abs(circle.center.x - (box.min.x + halfRectWidth)); + if (distX > (halfRectWidth + circle.radius)) { + return false; + } + + auto halfRectHeight = (box.max.y - box.min.y) / 2; + auto distY = std::abs(circle.center.y - (box.min.y + halfRectHeight)); + if (distY > (halfRectHeight + circle.radius)) { + return false; + } + + if (distX <= halfRectWidth || distY <= halfRectHeight) { + return true; + } + + auto dx = distX - halfRectWidth; + auto dy = distY - halfRectHeight; + return (dx * dx + dy * dy) <= (circle.radius * circle.radius); } template class GridIndex<IndexedSubfeature>; + } // namespace mbgl diff --git a/src/mbgl/util/grid_index.hpp b/src/mbgl/util/grid_index.hpp index 8ef8fb35b7..772aec6e38 100644 --- a/src/mbgl/util/grid_index.hpp +++ b/src/mbgl/util/grid_index.hpp @@ -6,32 +6,96 @@ #include <cstdint> #include <cstddef> #include <vector> +#include <functional> + +// TODO: Move into geometry.hpp project +namespace mapbox { +namespace geometry { + +template <typename T> +struct circle +{ + using point_type = point<T>; + + constexpr circle(point_type const& center_, T const& radius_) + : center(center_), radius(radius_) + {} + + point_type center; + T radius; +}; + +template <typename T> +constexpr bool operator==(circle<T> const& lhs, circle<T> const& rhs) +{ + return lhs.center == rhs.center && lhs.radius == rhs.radius; +} + +template <typename T> +constexpr bool operator!=(circle<T> const& lhs, circle<T> const& rhs) +{ + return lhs.center != rhs.center || lhs.radius != rhs.radius; +} + +} // namespace geometry +} // namespace mapbox namespace mbgl { +/* + GridIndex is a data structure for testing the intersection of + circles and rectangles in a 2d plane. + It is optimized for rapid insertion and querying. + GridIndex splits the plane into a set of "cells" and keeps track + of which geometries intersect with each cell. At query time, + full geometry comparisons are only done for items that share + at least one cell. As long as the geometries are relatively + uniformly distributed across the plane, this greatly reduces + the number of comparisons necessary. +*/ + template <class T> class GridIndex { public: - GridIndex(int32_t extent_, int32_t n_, int32_t padding_); + GridIndex(int32_t width_, int32_t height_, int32_t cellSize_); using BBox = mapbox::geometry::box<int16_t>; + using BCircle = mapbox::geometry::circle<int16_t>; void insert(T&& t, const BBox&); + void insert(T&& t, const BCircle&); + std::vector<T> query(const BBox&) const; + std::vector<T> query(const BCircle&) const; + + bool hitTest(const BBox&) const; + bool hitTest(const BCircle&) 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; + + void query(const BBox&, std::function<bool (const T&)>) const; + void query(const BCircle&, std::function<bool (const T&)>) const; + + int32_t convertToXCellCoord(int32_t x) const; + int32_t convertToYCellCoord(int32_t y) const; + + bool boxesCollide(const BBox&, const BBox&) const; + bool circlesCollide(const BCircle&, const BCircle&) const; + bool circleAndBoxCollide(const BCircle&, const BBox&) const; + + const int32_t width; + const int32_t height; + + const int16_t xCellCount; + const int16_t yCellCount; + const double xScale; + const double yScale; + + std::vector<std::pair<T, BBox>> boxElements; + std::vector<std::pair<T, BCircle>> circleElements; + + std::vector<std::vector<size_t>> boxCells; + std::vector<std::vector<size_t>> circleCells; }; |