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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
#include <mbgl/util/intersection_tests.hpp>
#include <mbgl/util/math.hpp>
namespace mbgl {
namespace util {
bool polygonContainsPoint(const GeometryCoordinates& ring, const GeometryCoordinate& p) {
bool c = false;
for (auto i = ring.begin(), j = ring.end() - 1; i != ring.end(); j = i++) {
auto& p1 = *i;
auto& p2 = *j;
if (((p1.y > p.y) != (p2.y > p.y)) && (p.x < float(p2.x - p1.x) * float(p.y - p1.y) / float(p2.y - p1.y) + p1.x)) {
c = !c;
}
}
return c;
}
// Code from http://stackoverflow.com/a/1501725/331379.
float distToSegmentSquared(const GeometryCoordinate& p, const GeometryCoordinate& v, const GeometryCoordinate& w) {
if (v == w) return util::distSqr<float>(p, v);
const auto l2 = util::distSqr<float>(v, w);
const float t = float((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
if (t < 0) return util::distSqr<float>(p, v);
if (t > 1) return util::distSqr<float>(p, w);
return util::distSqr<float>(p, convertPoint<float>(w - v) * t + convertPoint<float>(v));
}
bool pointIntersectsBufferedLine(const GeometryCoordinate& p, const GeometryCoordinates& line, const float radius) {
const float radiusSquared = radius * radius;
if (line.size() == 1) return util::distSqr<float>(p, line.at(0)) < radiusSquared;
if (line.size() == 0) return false;
for (auto i = line.begin() + 1; i != line.end(); i++) {
// Find line segments that have a distance <= radius^2 to p
// In that case, we treat the line as "containing point p".
auto& v = *(i - 1);
auto& w = *i;
if (distToSegmentSquared(p, v, w) < radiusSquared) return true;
}
return false;
}
// http://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
bool isCounterClockwise(const GeometryCoordinate& a, const GeometryCoordinate& b, const GeometryCoordinate& c) {
return (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.x);
}
bool lineSegmentIntersectsLineSegment(const GeometryCoordinate& a0, const GeometryCoordinate& a1, const GeometryCoordinate& b0, const GeometryCoordinate& b1) {
return isCounterClockwise(a0, b0, b1) != isCounterClockwise(a1, b0, b1) &&
isCounterClockwise(a0, a1, b0) != isCounterClockwise(a0, a1, b1);
}
bool lineIntersectsLine(const GeometryCoordinates& lineA, const GeometryCoordinates& lineB) {
if (lineA.size() == 0 || lineB.size() == 0) return false;
for (auto i = lineA.begin(); i != lineA.end() - 1; i++) {
auto& a0 = *i;
auto& a1 = *(i + 1);
for (auto j = lineB.begin(); j != lineB.end() - 1; j++) {
auto& b0 = *j;
auto& b1 = *(j + 1);
if (lineSegmentIntersectsLineSegment(a0, a1, b0, b1)) return true;
}
}
return false;
}
bool lineIntersectsBufferedLine(const GeometryCoordinates& lineA, const GeometryCoordinates& lineB, float radius) {
if (lineA.size() > 1) {
if (lineIntersectsLine(lineA, lineB)) return true;
// Check whether any point in either line is within radius of the other line
for (auto& p : lineB) {
if (pointIntersectsBufferedLine(p, lineA, radius)) return true;
}
}
for (auto& p : lineA) {
if (pointIntersectsBufferedLine(p, lineB, radius)) return true;
}
return false;
}
bool polygonIntersectsBufferedMultiPoint(const GeometryCoordinates& polygon, const GeometryCollection& rings, float radius) {
for (auto& ring : rings) {
for (auto& point : ring) {
if (polygonContainsPoint(polygon, point)) return true;
if (pointIntersectsBufferedLine(point, polygon, radius)) return true;
}
}
return false;
}
bool polygonIntersectsBufferedMultiLine(const GeometryCoordinates& polygon, const GeometryCollection& multiLine, float radius) {
for (auto& line : multiLine) {
if (polygon.size() >= 3) {
for (auto& p : line) {
if (polygonContainsPoint(polygon, p)) return true;
}
}
if (lineIntersectsBufferedLine(polygon, line, radius)) return true;
}
return false;
}
bool polygonIntersectsPolygon(const GeometryCoordinates& polygonA, const GeometryCoordinates& polygonB) {
for (auto& p : polygonA) {
if (polygonContainsPoint(polygonB, p)) return true;
}
for (auto& p : polygonB) {
if (polygonContainsPoint(polygonA, p)) return true;
}
if (lineIntersectsLine(polygonA, polygonB)) return true;
return false;
}
bool polygonIntersectsMultiPolygon(const GeometryCoordinates& polygon, const GeometryCollection& multiPolygon) {
for (auto& ring : multiPolygon) {
if (polygonIntersectsPolygon(polygon, ring)) return true;
}
return false;
}
} // namespace util
} // namespace mbgl
|
