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
|
#pragma once
#include <mapbox/geometry/point.hpp>
#include <mapbox/geometry/box.hpp>
#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(const float width_, const float height_, const int16_t cellSize_);
using BBox = mapbox::geometry::box<float>;
using BCircle = mapbox::geometry::circle<float>;
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;
bool empty() const;
private:
void query(const BBox&, std::function<bool (const T&)>) const;
void query(const BCircle&, std::function<bool (const T&)>) 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;
};
} // namespace mbgl
|
