diff options
author | Chris Loer <chris.loer@gmail.com> | 2017-11-09 13:24:43 -0800 |
---|---|---|
committer | Chris Loer <chris.loer@mapbox.com> | 2017-11-17 10:05:15 -0800 |
commit | 601a1c8dcf73f1a419c1ed5c39fbd14c581abf50 (patch) | |
tree | 46834b3601d9da910f929e1e5e916f6ac368b494 /src/mbgl/util/grid_index.hpp | |
parent | 31f0f47195ae7d4a6f96b1c64cd39e1268fdfc8d (diff) | |
download | qtlocation-mapboxgl-601a1c8dcf73f1a419c1ed5c39fbd14c581abf50.tar.gz |
[core] Add circle geometries to GridIndex.
- Adds early exiting "hitTest" query for fast collision detection
- GridIndex now determines cell count separately for x and y axes based on grid dimensions.
Diffstat (limited to 'src/mbgl/util/grid_index.hpp')
-rw-r--r-- | src/mbgl/util/grid_index.hpp | 96 |
1 files changed, 82 insertions, 14 deletions
diff --git a/src/mbgl/util/grid_index.hpp b/src/mbgl/util/grid_index.hpp index 8ef8fb35b7..6ef2966bee 100644 --- a/src/mbgl/util/grid_index.hpp +++ b/src/mbgl/util/grid_index.hpp @@ -6,32 +6,100 @@ #include <cstdint> #include <cstddef> #include <vector> +#include <functional> namespace mbgl { +namespace geometry { + +template <typename T> +struct circle +{ + using point_type = mapbox::geometry::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 + + +/* + 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_); - using BBox = mapbox::geometry::box<int16_t>; + GridIndex(const float width_, const float height_, const int16_t cellSize_); + + using BBox = mapbox::geometry::box<float>; + using BCircle = geometry::circle<float>; void insert(T&& t, const BBox&); + void insert(T&& t, const BCircle&); + std::vector<T> query(const BBox&) const; + std::vector<std::pair<T,BBox>> queryWithBoxes(const BBox&) const; + + bool hitTest(const BBox&) const; + bool hitTest(const BCircle&) const; + + bool empty() 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; + bool noIntersection(const BBox& queryBBox) const; + bool completeIntersection(const BBox& queryBBox) const; + BBox convertToBox(const BCircle& circle) const; + + void query(const BBox&, std::function<bool (const T&, const BBox&)>) const; + void query(const BCircle&, std::function<bool (const T&, const BBox&)>) const; + + int16_t convertToXCellCoord(const float x) const; + int16_t convertToYCellCoord(const float y) const; + + bool boxesCollide(const BBox&, const BBox&) const; + bool circlesCollide(const BCircle&, const BCircle&) const; + bool circleAndBoxCollide(const BCircle&, const BBox&) const; + + const float width; + const float 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; }; |