1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2R2RECT_H_
4#define UTIL_GEOMETRY_S2R2RECT_H_
5
6#include "base/basictypes.h"
7#include "base/logging.h"
8#include "r1interval.h"
9#include "s2region.h"
10#include "util/math/vector2-inl.h"
11
12class S2CellId;
13class S2Cell;
14
15// TODO: Create an r2.h and move this definition into it.
16typedef Vector2_d R2Point;
17
18// This class is a stopgap measure that allows some of the S2 spherical
19// geometry machinery to be applied to planar geometry. An S2R2Rect
20// represents a closed axis-aligned rectangle in the (x,y) plane, but it also
21// happens to be a subtype of S2Region, which means that you can use an
22// S2RegionCoverer to approximate it as a collection of S2CellIds.
23//
24// With respect to the S2Cell decomposition, an S2R2Rect is interpreted as a
25// region of (s,t)-space on face 0. In particular, the rectangle [0,1]x[0,1]
26// corresponds to the S2CellId that covers all of face 0. This means that
27// only rectangles that are subsets of [0,1]x[0,1] can be approximated using
28// the S2RegionCoverer interface.
29//
30// The S2R2Rect class is also a convenient way to find the (s,t)-region
31// covered by a given S2CellId (see the FromCell and FromCellId methods).
32//
33// TODO: If the geometry library is extended to have better support for planar
34// geometry, then this class should no longer be necessary.
35//
36// This class is intended to be copied by value as desired. It uses
37// the default copy constructor and assignment operator, however it is
38// not a "plain old datatype" (POD) because it has virtual functions.
39class S2R2Rect : public S2Region {
40 public:
41 // Construct a rectangle from the given lower-left and upper-right points.
42 inline S2R2Rect(R2Point const& lo, R2Point const& hi);
43
44 // Construct a rectangle from the given intervals in x and y. The two
45 // intervals must either be both empty or both non-empty.
46 inline S2R2Rect(R1Interval const& x, R1Interval const& y);
47
48 // Construct a rectangle that corresponds to the boundary of the given cell
49 // is (s,t)-space. Such rectangles are always a subset of [0,1]x[0,1].
50 static S2R2Rect FromCell(S2Cell const& cell);
51 static S2R2Rect FromCellId(S2CellId const& id);
52
53 // Construct a rectangle from a center point and size in each dimension.
54 // Both components of size should be non-negative, i.e. this method cannot
55 // be used to create an empty rectangle.
56 static S2R2Rect FromCenterSize(R2Point const& center,
57 R2Point const& size);
58
59 // Convenience method to construct a rectangle containing a single point.
60 static S2R2Rect FromPoint(R2Point const& p);
61
62 // Convenience method to construct the minimal bounding rectangle containing
63 // the two given points. This is equivalent to starting with an empty
64 // rectangle and calling AddPoint() twice. Note that it is different than
65 // the S2R2Rect(lo, hi) constructor, where the first point is always
66 // used as the lower-left corner of the resulting rectangle.
67 static S2R2Rect FromPointPair(R2Point const& p1, R2Point const& p2);
68
69 // Accessor methods.
70 R1Interval const& x() const { return x_; }
71 R1Interval const& y() const { return y_; }
72 R1Interval *mutable_x() { return &x_; }
73 R1Interval *mutable_y() { return &y_; }
74 R2Point lo() const { return R2Point(x_.lo(), y_.lo()); }
75 R2Point hi() const { return R2Point(x_.hi(), y_.hi()); }
76
77 // The canonical empty rectangle. Use is_empty() to test for empty
78 // rectangles, since they have more than one representation.
79 static inline S2R2Rect Empty();
80
81 // Return true if the rectangle is valid, which essentially just means
82 // that if the bound for either axis is empty then both must be.
83 inline bool is_valid() const;
84
85 // Return true if the rectangle is empty, i.e. it contains no points at all.
86 inline bool is_empty() const;
87
88 // Return the k-th vertex of the rectangle (k = 0,1,2,3) in CCW order.
89 // Vertex 0 is in the lower-left corner.
90 R2Point GetVertex(int k) const;
91
92 // Return the center of the rectangle in (x,y)-space
93 // (in general this is not the center of the region on the sphere).
94 R2Point GetCenter() const;
95
96 // Return the width and height of this rectangle in (x,y)-space. Empty
97 // rectangles have a negative width and height.
98 R2Point GetSize() const;
99
100 // Return true if the rectangle contains the given point. Note that
101 // rectangles are closed regions, i.e. they contain their boundary.
102 bool Contains(R2Point const& p) const;
103
104 // Return true if and only if the given point is contained in the interior
105 // of the region (i.e. the region excluding its boundary).
106 bool InteriorContains(R2Point const& p) const;
107
108 // Return true if and only if the rectangle contains the given other
109 // rectangle.
110 bool Contains(S2R2Rect const& other) const;
111
112 // Return true if and only if the interior of this rectangle contains all
113 // points of the given other rectangle (including its boundary).
114 bool InteriorContains(S2R2Rect const& other) const;
115
116 // Return true if this rectangle and the given other rectangle have any
117 // points in common.
118 bool Intersects(S2R2Rect const& other) const;
119
120 // Return true if and only if the interior of this rectangle intersects
121 // any point (including the boundary) of the given other rectangle.
122 bool InteriorIntersects(S2R2Rect const& other) const;
123
124 // Increase the size of the bounding rectangle to include the given point.
125 // The rectangle is expanded by the minimum amount possible.
126 void AddPoint(R2Point const& p);
127
128 // Return a rectangle that contains all points whose x-distance from this
129 // rectangle is at most margin.x(), and whose y-distance from this rectangle
130 // is at most margin.y(). Note that any expansion of an empty interval
131 // remains empty, and both components of the given margin must be
132 // non-negative.
133 S2R2Rect Expanded(R2Point const& margin) const;
134
135 // Return the smallest rectangle containing the union of this rectangle and
136 // the given rectangle.
137 S2R2Rect Union(S2R2Rect const& other) const;
138
139 // Return the smallest rectangle containing the intersection of this
140 // rectangle and the given rectangle.
141 S2R2Rect Intersection(S2R2Rect const& other) const;
142
143 // Return true if two rectangles contains the same set of points.
144 inline bool operator==(S2R2Rect const& other) const;
145
146 // Return true if the x- and y-intervals of the two rectangles are the same
147 // up to the given tolerance (see r1interval.h for details).
148 bool ApproxEquals(S2R2Rect const& other, double max_error = 1e-15) const;
149
150 // Return the unit-length S2Point corresponding to the given point "p" in
151 // the (s,t)-plane. "p" need not be restricted to the range [0,1]x[0,1].
152 static S2Point ToS2Point(R2Point const& p);
153
154 ////////////////////////////////////////////////////////////////////////
155 // S2Region interface (see s2region.h for details):
156
157 virtual S2R2Rect* Clone() const;
158 virtual S2Cap GetCapBound() const;
159 virtual S2LatLngRect GetRectBound() const;
160 virtual bool VirtualContainsPoint(S2Point const& p) const {
161 return Contains(p); // The same as Contains() below, just virtual.
162 }
163 bool Contains(S2Point const& p) const;
164 virtual bool Contains(S2Cell const& cell) const;
165 virtual bool MayIntersect(S2Cell const& cell) const;
166 virtual void Encode(Encoder* const encoder) const {
167 LOG(FATAL) << "Unimplemented";
168 }
169 virtual bool Decode(Decoder* const decoder) { return false; }
170
171 private:
172 R1Interval x_;
173 R1Interval y_;
174};
175
176inline S2R2Rect::S2R2Rect(R2Point const& lo, R2Point const& hi)
177 : x_(lo.x(), hi.x()), y_(lo.y(), hi.y()) {
178 DCHECK(is_valid());
179}
180
181inline S2R2Rect::S2R2Rect(R1Interval const& x, R1Interval const& y)
182 : x_(x), y_(y) {
183 DCHECK(is_valid());
184}
185
186inline S2R2Rect S2R2Rect::Empty() {
187 return S2R2Rect(R1Interval::Empty(), R1Interval::Empty());
188}
189
190inline bool S2R2Rect::is_valid() const {
191 // The x/y ranges must either be both empty or both non-empty.
192 return x_.is_empty() == y_.is_empty();
193}
194
195inline bool S2R2Rect::is_empty() const {
196 return x_.is_empty();
197}
198
199inline bool S2R2Rect::operator==(S2R2Rect const& other) const {
200 return x_ == other.x_ && y_ == other.y_;
201}
202
203ostream& operator<<(ostream& os, S2R2Rect const& r);
204
205#endif // UTIL_GEOMETRY_S2R2RECT_H_
206