1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#pragma once
#include <mapbox/geometry/point.hpp>
#include <mapbox/geometry/box.hpp>
#include <mbgl/util/optional.hpp>
#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(float width_, float height_, uint32_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&, optional<std::function<bool(const T&)>> predicate = nullopt) const;
bool hitTest(const BCircle&, optional<std::function<bool(const T&)>> predicate = nullopt) const;
bool empty() const;
private:
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;
std::size_t convertToXCellCoord(float x) const;
std::size_t convertToYCellCoord(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 std::size_t xCellCount;
const std::size_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;
};
} // namespace mbgl
|
