1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#include "s2r2rect.h"
4
5#include "base/logging.h"
6#include "r1interval.h"
7#include "s2.h"
8#include "s2cap.h"
9#include "s2cell.h"
10#include "s2latlngrect.h"
11
12S2R2Rect S2R2Rect::FromCell(S2Cell const& cell) {
13 // S2Cells have a more efficient GetSizeST() method than S2CellIds.
14 double size = cell.GetSizeST();
15 return FromCenterSize(cell.id().GetCenterST(), R2Point(size, size));
16}
17
18S2R2Rect S2R2Rect::FromCellId(S2CellId const& id) {
19 double size = id.GetSizeST();
20 return FromCenterSize(id.GetCenterST(), R2Point(size, size));
21}
22
23S2R2Rect S2R2Rect::FromCenterSize(R2Point const& center, R2Point const& size) {
24 return S2R2Rect(R1Interval(center.x() - 0.5 * size.x(),
25 center.x() + 0.5 * size.x()),
26 R1Interval(center.y() - 0.5 * size.y(),
27 center.y() + 0.5 * size.y()));
28}
29
30S2R2Rect S2R2Rect::FromPoint(R2Point const& p) {
31 return S2R2Rect(p, p);
32}
33
34S2R2Rect S2R2Rect::FromPointPair(R2Point const& p1, R2Point const& p2) {
35 return S2R2Rect(R1Interval::FromPointPair(p1.x(), p2.x()),
36 R1Interval::FromPointPair(p1.y(), p2.y()));
37}
38
39S2R2Rect* S2R2Rect::Clone() const {
40 return new S2R2Rect(*this);
41}
42
43R2Point S2R2Rect::GetVertex(int k) const {
44 // Twiddle bits to return the points in CCW order (SW, SE, NE, NW).
45 return R2Point(x_.bound((k>>1) ^ (k&1)), y_.bound(k>>1));
46}
47
48R2Point S2R2Rect::GetCenter() const {
49 return R2Point(x_.GetCenter(), y_.GetCenter());
50}
51
52R2Point S2R2Rect::GetSize() const {
53 return R2Point(x_.GetLength(), y_.GetLength());
54}
55
56bool S2R2Rect::Contains(R2Point const& p) const {
57 return x_.Contains(p.x()) && y_.Contains(p.y());
58}
59
60bool S2R2Rect::InteriorContains(R2Point const& p) const {
61 return x_.InteriorContains(p.x()) && y_.InteriorContains(p.y());
62}
63
64bool S2R2Rect::Contains(S2R2Rect const& other) const {
65 return x_.Contains(other.x_) && y_.Contains(other.y_);
66}
67
68bool S2R2Rect::InteriorContains(S2R2Rect const& other) const {
69 return x_.InteriorContains(other.x_) && y_.InteriorContains(other.y_);
70}
71
72bool S2R2Rect::Intersects(S2R2Rect const& other) const {
73 return x_.Intersects(other.x_) && y_.Intersects(other.y_);
74}
75
76bool S2R2Rect::InteriorIntersects(S2R2Rect const& other) const {
77 return x_.InteriorIntersects(other.x_) && y_.InteriorIntersects(other.y_);
78}
79
80void S2R2Rect::AddPoint(R2Point const& p) {
81 x_.AddPoint(p.x());
82 y_.AddPoint(p.y());
83}
84
85S2R2Rect S2R2Rect::Expanded(R2Point const& margin) const {
86 DCHECK_GE(margin.x(), 0);
87 DCHECK_GE(margin.y(), 0);
88 return S2R2Rect(x_.Expanded(margin.x()), y_.Expanded(margin.y()));
89}
90
91S2R2Rect S2R2Rect::Union(S2R2Rect const& other) const {
92 return S2R2Rect(x_.Union(other.x_), y_.Union(other.y_));
93}
94
95S2R2Rect S2R2Rect::Intersection(S2R2Rect const& other) const {
96 R1Interval x = x_.Intersection(other.x_);
97 R1Interval y = y_.Intersection(other.y_);
98 if (x.is_empty() || y.is_empty()) {
99 // The x/y ranges must either be both empty or both non-empty.
100 return Empty();
101 }
102 return S2R2Rect(x, y);
103}
104
105bool S2R2Rect::ApproxEquals(S2R2Rect const& other, double max_error) const {
106 return (x_.ApproxEquals(other.x_, max_error) &&
107 y_.ApproxEquals(other.y_, max_error));
108}
109
110S2Point S2R2Rect::ToS2Point(R2Point const& p) {
111 return S2::FaceUVtoXYZ(0, S2::STtoUV(p.x()), S2::STtoUV(p.y())).Normalize();
112}
113
114S2Cap S2R2Rect::GetCapBound() const {
115 if (is_empty()) return S2Cap::Empty();
116
117 // The rectangle is a convex polygon on the sphere, since it is a subset of
118 // one cube face. Its bounding cap is also a convex region on the sphere,
119 // and therefore we can bound the rectangle by just bounding its vertices.
120 // We use the rectangle's center in (s,t)-space as the cap axis. This
121 // doesn't yield the minimal cap but it's pretty close.
122 S2Cap cap = S2Cap::FromAxisHeight(ToS2Point(GetCenter()), 0);
123 for (int k = 0; k < 4; ++k) {
124 cap.AddPoint(ToS2Point(GetVertex(k)));
125 }
126 return cap;
127}
128
129S2LatLngRect S2R2Rect::GetRectBound() const {
130 // This is not very tight but hopefully good enough.
131 return GetCapBound().GetRectBound();
132}
133
134bool S2R2Rect::Contains(S2Point const& p) const {
135 S2CellId cellid = S2CellId::FromPoint(p);
136 if (cellid.face() != 0) return false;
137 return Contains(cellid.GetCenterST());
138}
139
140bool S2R2Rect::Contains(S2Cell const& cell) const {
141 if (cell.face() != 0) return false;
142 return Contains(S2R2Rect::FromCell(cell));
143}
144
145bool S2R2Rect::MayIntersect(S2Cell const& cell) const {
146 if (cell.face() != 0) return false;
147 return Intersects(S2R2Rect::FromCell(cell));
148}
149
150ostream& operator<<(ostream& os, S2R2Rect const& r) {
151 return os << "[Lo" << r.lo() << ", Hi" << r.hi() << "]";
152}
153