1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2LATLNGRECT_H_
4#define UTIL_GEOMETRY_S2LATLNGRECT_H_
5
6#include <iostream>
7using std::ostream;
8using std::cout;
9using std::endl;
10
11
12#include "base/basictypes.h"
13#include "base/logging.h"
14#include "s1angle.h"
15#include "r1interval.h"
16#include "s1interval.h"
17#include "s2region.h"
18#include "s2latlng.h"
19
20// An S2LatLngRect represents a closed latitude-longitude rectangle. It is
21// capable of representing the empty and full rectangles as well as
22// single points.
23//
24// This class is intended to be copied by value as desired. It uses
25// the default copy constructor and assignment operator, however it is
26// not a "plain old datatype" (POD) because it has virtual functions.
27class S2LatLngRect : public S2Region {
28 public:
29 // Construct a rectangle from minimum and maximum latitudes and longitudes.
30 // If lo.lng() > hi.lng(), the rectangle spans the 180 degree longitude
31 // line. Both points must be normalized, with lo.lat() <= hi.lat().
32 // The rectangle contains all the points p such that 'lo' <= p <= 'hi',
33 // where '<=' is defined in the obvious way.
34 inline S2LatLngRect(S2LatLng const& lo, S2LatLng const& hi);
35
36 // Construct a rectangle from latitude and longitude intervals. The two
37 // intervals must either be both empty or both non-empty, and the latitude
38 // interval must not extend outside [-90, +90] degrees.
39 // Note that both intervals (and hence the rectangle) are closed.
40 inline S2LatLngRect(R1Interval const& lat, S1Interval const& lng);
41
42 // The default constructor creates an empty S2LatLngRect.
43 inline S2LatLngRect();
44
45 // Construct a rectangle of the given size centered around the given point.
46 // "center" needs to be normalized, but "size" does not. The latitude
47 // interval of the result is clamped to [-90,90] degrees, and the longitude
48 // interval of the result is Full() if and only if the longitude size is
49 // 360 degrees or more. Examples of clamping (in degrees):
50 //
51 // center=(80,170), size=(40,60) -> lat=[60,90], lng=[140,-160]
52 // center=(10,40), size=(210,400) -> lat=[-90,90], lng=[-180,180]
53 // center=(-90,180), size=(20,50) -> lat=[-90,-80], lng=[155,-155]
54 static S2LatLngRect FromCenterSize(S2LatLng const& center,
55 S2LatLng const& size);
56
57 // Construct a rectangle containing a single (normalized) point.
58 static S2LatLngRect FromPoint(S2LatLng const& p);
59
60 // Construct the minimal bounding rectangle containing the two given
61 // normalized points. This is equivalent to starting with an empty
62 // rectangle and calling AddPoint() twice. Note that it is different than
63 // the S2LatLngRect(lo, hi) constructor, where the first point is always
64 // used as the lower-left corner of the resulting rectangle.
65 static S2LatLngRect FromPointPair(S2LatLng const& p1, S2LatLng const& p2);
66
67 // Accessor methods.
68 S1Angle lat_lo() const { return S1Angle::Radians(lat_.lo()); }
69 S1Angle lat_hi() const { return S1Angle::Radians(lat_.hi()); }
70 S1Angle lng_lo() const { return S1Angle::Radians(lng_.lo()); }
71 S1Angle lng_hi() const { return S1Angle::Radians(lng_.hi()); }
72 R1Interval const& lat() const { return lat_; }
73 S1Interval const& lng() const { return lng_; }
74 R1Interval *mutable_lat() { return &lat_; }
75 S1Interval *mutable_lng() { return &lng_; }
76 S2LatLng lo() const { return S2LatLng(lat_lo(), lng_lo()); }
77 S2LatLng hi() const { return S2LatLng(lat_hi(), lng_hi()); }
78
79 // The canonical empty and full rectangles.
80 static inline S2LatLngRect Empty();
81 static inline S2LatLngRect Full();
82
83 // The full allowable range of latitudes and longitudes.
84 static R1Interval FullLat() { return R1Interval(-M_PI_2, M_PI_2); }
85 static S1Interval FullLng() { return S1Interval::Full(); }
86
87 // Return true if the rectangle is valid, which essentially just means
88 // that the latitude bounds do not exceed Pi/2 in absolute value and
89 // the longitude bounds do not exceed Pi in absolute value. Also, if
90 // either the latitude or longitude bound is empty then both must be.
91 inline bool is_valid() const;
92
93 // Return true if the rectangle is empty, i.e. it contains no points at all.
94 inline bool is_empty() const;
95
96 // Return true if the rectangle is full, i.e. it contains all points.
97 inline bool is_full() const;
98
99 // Return true if the rectangle is a point, i.e. lo() == hi()
100 inline bool is_point() const;
101
102 // Return true if lng_.lo() > lng_.hi(), i.e. the rectangle crosses
103 // the 180 degree longitude line.
104 bool is_inverted() const { return lng_.is_inverted(); }
105
106 // Return the k-th vertex of the rectangle (k = 0,1,2,3) in CCW order.
107 S2LatLng GetVertex(int k) const;
108
109 // Return the center of the rectangle in latitude-longitude space
110 // (in general this is not the center of the region on the sphere).
111 S2LatLng GetCenter() const;
112
113 // Return the width and height of this rectangle in latitude-longitude
114 // space. Empty rectangles have a negative width and height.
115 S2LatLng GetSize() const;
116
117 // Returns the surface area of this rectangle on the unit sphere.
118 double Area() const;
119
120 // More efficient version of Contains() that accepts a S2LatLng rather than
121 // an S2Point. The argument must be normalized.
122 bool Contains(S2LatLng const& ll) const;
123
124 // Return true if and only if the given point is contained in the interior
125 // of the region (i.e. the region excluding its boundary). The point 'p'
126 // does not need to be normalized.
127 bool InteriorContains(S2Point const& p) const;
128
129 // More efficient version of InteriorContains() that accepts a S2LatLng
130 // rather than an S2Point. The argument must be normalized.
131 bool InteriorContains(S2LatLng const& ll) const;
132
133 // Return true if and only if the rectangle contains the given other
134 // rectangle.
135 bool Contains(S2LatLngRect const& other) const;
136
137 // Return true if and only if the interior of this rectangle contains all
138 // points of the given other rectangle (including its boundary).
139 bool InteriorContains(S2LatLngRect const& other) const;
140
141 // Return true if this rectangle and the given other rectangle have any
142 // points in common.
143 bool Intersects(S2LatLngRect const& other) const;
144
145 // Returns true if this rectangle intersects the given cell. (This is an
146 // exact test and may be fairly expensive, see also MayIntersect below.)
147 bool Intersects(S2Cell const& cell) const;
148
149 // Return true if and only if the interior of this rectangle intersects
150 // any point (including the boundary) of the given other rectangle.
151 bool InteriorIntersects(S2LatLngRect const& other) const;
152
153 // Increase the size of the bounding rectangle to include the given point.
154 // The rectangle is expanded by the minimum amount possible. The S2LatLng
155 // argument must be normalized.
156 void AddPoint(S2Point const& p);
157 void AddPoint(S2LatLng const& ll);
158
159 // Return a rectangle that contains all points whose latitude distance from
160 // this rectangle is at most margin.lat(), and whose longitude distance
161 // from this rectangle is at most margin.lng(). In particular, latitudes
162 // are clamped while longitudes are wrapped. Note that any expansion of an
163 // empty interval remains empty, and both components of the given margin
164 // must be non-negative. "margin" does not need to be normalized.
165 //
166 // NOTE: If you are trying to grow a rectangle by a certain *distance* on
167 // the sphere (e.g. 5km), use the ConvolveWithCap() method instead.
168 S2LatLngRect Expanded(S2LatLng const& margin) const;
169
170 // Return the smallest rectangle containing the union of this rectangle and
171 // the given rectangle.
172 S2LatLngRect Union(S2LatLngRect const& other) const;
173
174 // Return the smallest rectangle containing the intersection of this
175 // rectangle and the given rectangle. Note that the region of intersection
176 // may consist of two disjoint rectangles, in which case a single rectangle
177 // spanning both of them is returned.
178 S2LatLngRect Intersection(S2LatLngRect const& other) const;
179
180 // Return a rectangle that contains the convolution of this rectangle with a
181 // cap of the given angle. This expands the rectangle by a fixed distance
182 // (as opposed to growing the rectangle in latitude-longitude space). The
183 // returned rectangle includes all points whose minimum distance to the
184 // original rectangle is at most the given angle.
185 S2LatLngRect ConvolveWithCap(S1Angle const& angle) const;
186
187 // Returns the minimum distance (measured along the surface of the sphere) to
188 // the given S2LatLngRect. Both S2LatLngRects must be non-empty.
189 S1Angle GetDistance(S2LatLngRect const& other) const;
190
191 // Returns the minimum distance (measured along the surface of the sphere)
192 // from a given point to the rectangle (both its boundary and its interior).
193 // The latlng must be valid.
194 S1Angle GetDistance(S2LatLng const& p) const;
195
196 // Returns the (directed or undirected) Hausdorff distance (measured along the
197 // surface of the sphere) to the given S2LatLngRect. The directed Hausdorff
198 // distance from rectangle A to rectangle B is given by
199 // h(A, B) = max_{p in A} min_{q in B} d(p, q).
200 // The Hausdorff distance between rectangle A and rectangle B is given by
201 // H(A, B) = max{h(A, B), h(B, A)}.
202 S1Angle GetDirectedHausdorffDistance(S2LatLngRect const& other) const;
203 S1Angle GetHausdorffDistance(S2LatLngRect const& other) const;
204
205 // Return true if two rectangles contains the same set of points.
206 inline bool operator==(S2LatLngRect const& other) const;
207
208 // Return the opposite of what operator == returns.
209 inline bool operator!=(S2LatLngRect const& other) const;
210
211 // Return true if the latitude and longitude intervals of the two rectangles
212 // are the same up to the given tolerance (see r1interval.h and s1interval.h
213 // for details).
214 bool ApproxEquals(S2LatLngRect const& other, double max_error = 1e-15) const;
215
216 ////////////////////////////////////////////////////////////////////////
217 // S2Region interface (see s2region.h for details):
218
219 virtual S2LatLngRect* Clone() const;
220 virtual S2Cap GetCapBound() const;
221 virtual S2LatLngRect GetRectBound() const;
222 virtual bool Contains(S2Cell const& cell) const;
223 virtual bool VirtualContainsPoint(S2Point const& p) const {
224 return Contains(p); // The same as Contains() below, just virtual.
225 }
226
227 // This test is cheap but is NOT exact. Use Intersects() if you want a more
228 // accurate and more expensive test. Note that when this method is used by
229 // an S2RegionCoverer, the accuracy isn't all that important since if a cell
230 // may intersect the region then it is subdivided, and the accuracy of this
231 // method goes up as the cells get smaller.
232 virtual bool MayIntersect(S2Cell const& cell) const;
233
234 // The point 'p' does not need to be normalized.
235 bool Contains(S2Point const& p) const;
236
237 virtual void Encode(Encoder* const encoder) const;
238 virtual bool Decode(Decoder* const decoder);
239
240 private:
241 // Return true if the edge AB intersects the given edge of constant
242 // longitude.
243 static bool IntersectsLngEdge(S2Point const& a, S2Point const& b,
244 R1Interval const& lat, double lng);
245
246 // Return true if the edge AB intersects the given edge of constant
247 // latitude.
248 static bool IntersectsLatEdge(S2Point const& a, S2Point const& b,
249 double lat, S1Interval const& lng);
250
251 // Helper function. See .cc for description.
252 static S1Angle GetDirectedHausdorffDistance(double lng_diff,
253 R1Interval const& a_lat,
254 R1Interval const& b_lat);
255
256 // Helper function. See .cc for description.
257 static S1Angle GetInteriorMaxDistance(R1Interval const& a_lat,
258 S2Point const& b);
259
260 // Helper function. See .cc for description.
261 static S2Point GetBisectorIntersection(R1Interval const& lat, double lng);
262
263 R1Interval lat_;
264 S1Interval lng_;
265};
266
267inline S2LatLngRect::S2LatLngRect(S2LatLng const& lo, S2LatLng const& hi)
268 : lat_(lo.lat().radians(), hi.lat().radians()),
269 lng_(lo.lng().radians(), hi.lng().radians()) {
270 DCHECK(is_valid()) << lo << ", " << hi;
271}
272
273inline S2LatLngRect::S2LatLngRect(R1Interval const& lat, S1Interval const& lng)
274 : lat_(lat), lng_(lng) {
275 DCHECK(is_valid()) << lat << ", " << lng;
276}
277
278inline S2LatLngRect::S2LatLngRect()
279 : lat_(R1Interval::Empty()), lng_(S1Interval::Empty()) {
280}
281
282inline S2LatLngRect S2LatLngRect::Empty() {
283 return S2LatLngRect();
284}
285
286inline S2LatLngRect S2LatLngRect::Full() {
287 return S2LatLngRect(FullLat(), FullLng());
288}
289
290inline bool S2LatLngRect::is_valid() const {
291 // The lat/lng ranges must either be both empty or both non-empty.
292 return (fabs(lat_.lo()) <= M_PI_2 &&
293 fabs(lat_.hi()) <= M_PI_2 &&
294 lng_.is_valid() &&
295 lat_.is_empty() == lng_.is_empty());
296}
297
298inline bool S2LatLngRect::is_empty() const {
299 return lat_.is_empty();
300}
301
302inline bool S2LatLngRect::is_full() const {
303 return lat_ == FullLat() && lng_.is_full();
304}
305
306inline bool S2LatLngRect::is_point() const {
307 return lat_.lo() == lat_.hi() && lng_.lo() == lng_.hi();
308}
309
310inline bool S2LatLngRect::operator==(S2LatLngRect const& other) const {
311 return lat() == other.lat() && lng() == other.lng();
312}
313
314inline bool S2LatLngRect::operator!=(S2LatLngRect const& other) const {
315 return !operator==(other);
316}
317
318ostream& operator<<(ostream& os, S2LatLngRect const& r);
319
320#endif // UTIL_GEOMETRY_S2LATLNGRECT_H_
321