1 // Copyright 2005 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15
16 // Author: ericv@google.com (Eric Veach)
17
18 #ifndef S2_S2CELL_H_
19 #define S2_S2CELL_H_
20
21 #include "s2/base/integral_types.h"
22 #include "s2/base/logging.h"
23 #include "s2/_fp_contract_off.h"
24 #include "s2/r2rect.h"
25 #include "s2/s1chord_angle.h"
26 #include "s2/s2cell_id.h"
27 #include "s2/s2region.h"
28 #include "s2/util/math/vector.h"
29
30 class Decoder;
31 class Encoder;
32 class S2Cap;
33 class S2LatLng;
34 class S2LatLngRect;
35
36 // An S2Cell is an S2Region object that represents a cell. Unlike S2CellIds,
37 // it supports efficient containment and intersection tests. However, it is
38 // also a more expensive representation (currently 48 bytes rather than 8).
39
40 // This class is intended to be copied by value as desired. It uses
41 // the default copy constructor and assignment operator, however it is
42 // not a "plain old datatype" (POD) because it has virtual functions.
43 class S2Cell final : public S2Region {
44 public:
45 // The default constructor is required in order to use freelists.
46 // Cells should otherwise always be constructed explicitly.
S2Cell()47 S2Cell() {}
48
49 // An S2Cell always corresponds to a particular S2CellId. The other
50 // constructors are just convenience methods.
51 explicit S2Cell(S2CellId id);
52
53 // Convenience constructors. The S2LatLng must be normalized.
S2Cell(const S2Point & p)54 explicit S2Cell(const S2Point& p) : S2Cell(S2CellId(p)) {}
S2Cell(const S2LatLng & ll)55 explicit S2Cell(const S2LatLng& ll) : S2Cell(S2CellId(ll)) {}
56
57 // Returns the cell corresponding to the given S2 cube face.
FromFace(int face)58 static S2Cell FromFace(int face) {
59 return S2Cell(S2CellId::FromFace(face));
60 }
61
62 // Returns a cell given its face (range 0..5), Hilbert curve position within
63 // that face (an unsigned integer with S2CellId::kPosBits bits), and level
64 // (range 0..kMaxLevel). The given position will be modified to correspond
65 // to the Hilbert curve position at the center of the returned cell. This
66 // is a static function rather than a constructor in order to indicate what
67 // the arguments represent.
FromFacePosLevel(int face,uint64 pos,int level)68 static S2Cell FromFacePosLevel(int face, uint64 pos, int level) {
69 return S2Cell(S2CellId::FromFacePosLevel(face, pos, level));
70 }
71
id()72 S2CellId id() const { return id_; }
face()73 int face() const { return face_; }
level()74 int level() const { return level_; }
orientation()75 int orientation() const { return orientation_; }
is_leaf()76 bool is_leaf() const { return level_ == S2CellId::kMaxLevel; }
77
78 // These are equivalent to the S2CellId methods, but have a more efficient
79 // implementation since the level has been precomputed.
80 int GetSizeIJ() const;
81 double GetSizeST() const;
82
83 // Returns the k-th vertex of the cell (k = 0,1,2,3). Vertices are returned
84 // in CCW order (lower left, lower right, upper right, upper left in the UV
85 // plane). The points returned by GetVertexRaw are not normalized.
86 // For convenience, the argument is reduced modulo 4 to the range [0..3].
GetVertex(int k)87 S2Point GetVertex(int k) const { return GetVertexRaw(k).Normalize(); }
88 S2Point GetVertexRaw(int k) const;
89
90 // Returns the inward-facing normal of the great circle passing through the
91 // edge from vertex k to vertex k+1 (mod 4). The normals returned by
92 // GetEdgeRaw are not necessarily unit length. For convenience, the
93 // argument is reduced modulo 4 to the range [0..3].
GetEdge(int k)94 S2Point GetEdge(int k) const { return GetEdgeRaw(k).Normalize(); }
95 S2Point GetEdgeRaw(int k) const;
96
97 // If this is not a leaf cell, sets children[0..3] to the four children of
98 // this cell (in traversal order) and return true. Otherwise returns false.
99 // This method is equivalent to the following:
100 //
101 // for (pos=0, id=child_begin(); id != child_end(); id = id.next(), ++pos)
102 // children[pos] = S2Cell(id);
103 //
104 // except that it is more than two times faster.
105 bool Subdivide(S2Cell children[4]) const;
106
107 // Returns the direction vector corresponding to the center in (s,t)-space of
108 // the given cell. This is the point at which the cell is divided into four
109 // subcells; it is not necessarily the centroid of the cell in (u,v)-space
110 // or (x,y,z)-space. The point returned by GetCenterRaw is not necessarily
111 // unit length.
GetCenter()112 S2Point GetCenter() const { return GetCenterRaw().Normalize(); }
113 S2Point GetCenterRaw() const;
114
115 // Returns the average area for cells at the given level.
116 static double AverageArea(int level);
117
118 // Returns the average area of cells at this level in steradians. This is
119 // accurate to within a factor of 1.7 (for S2_QUADRATIC_PROJECTION) and is
120 // extremely cheap to compute.
AverageArea()121 double AverageArea() const { return AverageArea(level_); }
122
123 // Returns the approximate area of this cell in steradians. This method is
124 // accurate to within 3% percent for all cell sizes and accurate to within
125 // 0.1% for cells at level 5 or higher (i.e. squares 350km to a side or
126 // smaller on the Earth's surface). It is moderately cheap to compute.
127 double ApproxArea() const;
128
129 // Returns the area of this cell as accurately as possible. This method is
130 // more expensive but it is accurate to 6 digits of precision even for leaf
131 // cells (whose area is approximately 1e-18).
132 double ExactArea() const;
133
134 // Returns the bounds of this cell in (u,v)-space.
GetBoundUV()135 R2Rect GetBoundUV() const { return uv_; }
136
137 // Returns the distance from the cell to the given point. Returns zero if
138 // the point is inside the cell.
139 S1ChordAngle GetDistance(const S2Point& target) const;
140
141 // Return the distance from the cell boundary to the given point.
142 S1ChordAngle GetBoundaryDistance(const S2Point& target) const;
143
144 // Returns the maximum distance from the cell (including its interior) to the
145 // given point.
146 S1ChordAngle GetMaxDistance(const S2Point& target) const;
147
148 // Returns the minimum distance from the cell to the given edge AB. Returns
149 // zero if the edge intersects the cell interior.
150 S1ChordAngle GetDistance(const S2Point& a, const S2Point& b) const;
151
152 // Returns the maximum distance from the cell (including its interior) to the
153 // given edge AB.
154 S1ChordAngle GetMaxDistance(const S2Point& a, const S2Point& b) const;
155
156 // Returns the distance from the cell to the given cell. Returns zero if
157 // one cell contains the other.
158 S1ChordAngle GetDistance(const S2Cell& target) const;
159
160 // Returns the maximum distance from the cell (including its interior) to the
161 // given target cell.
162 S1ChordAngle GetMaxDistance(const S2Cell& target) const;
163
164 ////////////////////////////////////////////////////////////////////////
165 // S2Region interface (see s2region.h for details):
166
167 S2Cell* Clone() const override;
168 S2Cap GetCapBound() const override;
169 S2LatLngRect GetRectBound() const override;
170 bool Contains(const S2Cell& cell) const override;
171 bool MayIntersect(const S2Cell& cell) const override;
172
173 // Returns true if the cell contains the given point "p". Note that unlike
174 // S2Loop/S2Polygon, S2Cells are considered to be closed sets. This means
175 // that points along an S2Cell edge (or at a vertex) belong to the adjacent
176 // cell(s) as well.
177 //
178 // If instead you want every point to be contained by exactly one S2Cell,
179 // you will need to convert the S2Cells to S2Loops (which implement point
180 // containment this way).
181 //
182 // The point "p" does not need to be normalized.
183 bool Contains(const S2Point& p) const override;
184
185 // Appends a serialized representation of the S2Cell to "encoder".
186 //
187 // REQUIRES: "encoder" uses the default constructor, so that its buffer
188 // can be enlarged as necessary by calling Ensure(int).
189 void Encode(Encoder* const encoder) const;
190
191 // Decodes an S2Cell encoded with Encode(). Returns true on success.
192 bool Decode(Decoder* const decoder);
193
194 private:
195 // Returns the latitude or longitude of the cell vertex given by (i,j),
196 // where "i" and "j" are either 0 or 1.
197 double GetLatitude(int i, int j) const;
198 double GetLongitude(int i, int j) const;
199
200 S1ChordAngle VertexChordDist(const S2Point& p, int i, int j) const;
201 bool UEdgeIsClosest(const S2Point& target, int v_end) const;
202 bool VEdgeIsClosest(const S2Point& target, int u_end) const;
203
204 // Returns the distance from the given point to the interior of the cell if
205 // "to_interior" is true, and to the boundary of the cell otherwise.
206 S1ChordAngle GetDistanceInternal(const S2Point& target_xyz,
207 bool to_interior) const;
208
209 // This structure occupies 44 bytes plus one pointer for the vtable.
210 int8 face_;
211 int8 level_;
212 int8 orientation_;
213 S2CellId id_;
214 R2Rect uv_;
215 };
216
217 inline bool operator==(const S2Cell& x, const S2Cell& y) {
218 return x.id() == y.id();
219 }
220
221 inline bool operator!=(const S2Cell& x, const S2Cell& y) {
222 return x.id() != y.id();
223 }
224
225 inline bool operator<(const S2Cell& x, const S2Cell& y) {
226 return x.id() < y.id();
227 }
228
229 inline bool operator>(const S2Cell& x, const S2Cell& y) {
230 return x.id() > y.id();
231 }
232
233 inline bool operator<=(const S2Cell& x, const S2Cell& y) {
234 return x.id() <= y.id();
235 }
236
237 inline bool operator>=(const S2Cell& x, const S2Cell& y) {
238 return x.id() >= y.id();
239 }
240
GetSizeIJ()241 inline int S2Cell::GetSizeIJ() const {
242 return S2CellId::GetSizeIJ(level());
243 }
244
GetSizeST()245 inline double S2Cell::GetSizeST() const {
246 return S2CellId::GetSizeST(level());
247 }
248
249 #endif // S2_S2CELL_H_
250