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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
// Copyright 2005 Google Inc. All Rights Reserved.
#include "s2r2rect.h"
#include "base/logging.h"
#include "r1interval.h"
#include "s2.h"
#include "s2cap.h"
#include "s2cell.h"
#include "s2latlngrect.h"
S2R2Rect S2R2Rect::FromCell(S2Cell const& cell) {
// S2Cells have a more efficient GetSizeST() method than S2CellIds.
double size = cell.GetSizeST();
return FromCenterSize(cell.id().GetCenterST(), R2Point(size, size));
}
S2R2Rect S2R2Rect::FromCellId(S2CellId const& id) {
double size = id.GetSizeST();
return FromCenterSize(id.GetCenterST(), R2Point(size, size));
}
S2R2Rect S2R2Rect::FromCenterSize(R2Point const& center, R2Point const& size) {
return S2R2Rect(R1Interval(center.x() - 0.5 * size.x(),
center.x() + 0.5 * size.x()),
R1Interval(center.y() - 0.5 * size.y(),
center.y() + 0.5 * size.y()));
}
S2R2Rect S2R2Rect::FromPoint(R2Point const& p) {
return S2R2Rect(p, p);
}
S2R2Rect S2R2Rect::FromPointPair(R2Point const& p1, R2Point const& p2) {
return S2R2Rect(R1Interval::FromPointPair(p1.x(), p2.x()),
R1Interval::FromPointPair(p1.y(), p2.y()));
}
S2R2Rect* S2R2Rect::Clone() const {
return new S2R2Rect(*this);
}
R2Point S2R2Rect::GetVertex(int k) const {
// Twiddle bits to return the points in CCW order (SW, SE, NE, NW).
return R2Point(x_.bound((k>>1) ^ (k&1)), y_.bound(k>>1));
}
R2Point S2R2Rect::GetCenter() const {
return R2Point(x_.GetCenter(), y_.GetCenter());
}
R2Point S2R2Rect::GetSize() const {
return R2Point(x_.GetLength(), y_.GetLength());
}
bool S2R2Rect::Contains(R2Point const& p) const {
return x_.Contains(p.x()) && y_.Contains(p.y());
}
bool S2R2Rect::InteriorContains(R2Point const& p) const {
return x_.InteriorContains(p.x()) && y_.InteriorContains(p.y());
}
bool S2R2Rect::Contains(S2R2Rect const& other) const {
return x_.Contains(other.x_) && y_.Contains(other.y_);
}
bool S2R2Rect::InteriorContains(S2R2Rect const& other) const {
return x_.InteriorContains(other.x_) && y_.InteriorContains(other.y_);
}
bool S2R2Rect::Intersects(S2R2Rect const& other) const {
return x_.Intersects(other.x_) && y_.Intersects(other.y_);
}
bool S2R2Rect::InteriorIntersects(S2R2Rect const& other) const {
return x_.InteriorIntersects(other.x_) && y_.InteriorIntersects(other.y_);
}
void S2R2Rect::AddPoint(R2Point const& p) {
x_.AddPoint(p.x());
y_.AddPoint(p.y());
}
S2R2Rect S2R2Rect::Expanded(R2Point const& margin) const {
DCHECK_GE(margin.x(), 0);
DCHECK_GE(margin.y(), 0);
return S2R2Rect(x_.Expanded(margin.x()), y_.Expanded(margin.y()));
}
S2R2Rect S2R2Rect::Union(S2R2Rect const& other) const {
return S2R2Rect(x_.Union(other.x_), y_.Union(other.y_));
}
S2R2Rect S2R2Rect::Intersection(S2R2Rect const& other) const {
R1Interval x = x_.Intersection(other.x_);
R1Interval y = y_.Intersection(other.y_);
if (x.is_empty() || y.is_empty()) {
// The x/y ranges must either be both empty or both non-empty.
return Empty();
}
return S2R2Rect(x, y);
}
bool S2R2Rect::ApproxEquals(S2R2Rect const& other, double max_error) const {
return (x_.ApproxEquals(other.x_, max_error) &&
y_.ApproxEquals(other.y_, max_error));
}
S2Point S2R2Rect::ToS2Point(R2Point const& p) {
return S2::FaceUVtoXYZ(0, S2::STtoUV(p.x()), S2::STtoUV(p.y())).Normalize();
}
S2Cap S2R2Rect::GetCapBound() const {
if (is_empty()) return S2Cap::Empty();
// The rectangle is a convex polygon on the sphere, since it is a subset of
// one cube face. Its bounding cap is also a convex region on the sphere,
// and therefore we can bound the rectangle by just bounding its vertices.
// We use the rectangle's center in (s,t)-space as the cap axis. This
// doesn't yield the minimal cap but it's pretty close.
S2Cap cap = S2Cap::FromAxisHeight(ToS2Point(GetCenter()), 0);
for (int k = 0; k < 4; ++k) {
cap.AddPoint(ToS2Point(GetVertex(k)));
}
return cap;
}
S2LatLngRect S2R2Rect::GetRectBound() const {
// This is not very tight but hopefully good enough.
return GetCapBound().GetRectBound();
}
bool S2R2Rect::Contains(S2Point const& p) const {
S2CellId cellid = S2CellId::FromPoint(p);
if (cellid.face() != 0) return false;
return Contains(cellid.GetCenterST());
}
bool S2R2Rect::Contains(S2Cell const& cell) const {
if (cell.face() != 0) return false;
return Contains(S2R2Rect::FromCell(cell));
}
bool S2R2Rect::MayIntersect(S2Cell const& cell) const {
if (cell.face() != 0) return false;
return Intersects(S2R2Rect::FromCell(cell));
}
ostream& operator<<(ostream& os, S2R2Rect const& r) {
return os << "[Lo" << r.lo() << ", Hi" << r.hi() << "]";
}
|
