1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2CELL_H_
4#define UTIL_GEOMETRY_S2CELL_H_
5
6#include "base/basictypes.h"
7#include "base/logging.h"
8#include "s2.h"
9#include "s2cellid.h"
10#include "s2region.h"
11#include "util/math/vector2.h"
12
13// An S2Cell is an S2Region object that represents a cell. Unlike S2CellIds,
14// it supports efficient containment and intersection tests. However, it is
15// also a more expensive representation (currently 48 bytes rather than 8).
16
17// This class is intended to be copied by value as desired. It uses
18// the default copy constructor and assignment operator, however it is
19// not a "plain old datatype" (POD) because it has virtual functions.
20class S2Cell : public S2Region {
21 public:
22 // The default constructor is required in order to use freelists.
23 // Cells should otherwise always be constructed explicitly.
24 S2Cell() {}
25
26 // An S2Cell always corresponds to a particular S2CellId. The other
27 // constructors are just convenience methods.
28 explicit S2Cell(S2CellId const& id) { Init(id); }
29
30 static S2Cell FromFacePosLevel(int face, uint64 pos, int level) {
31 // This is a static method in order to provide named parameters.
32 return S2Cell(S2CellId::FromFacePosLevel(face, pos, level));
33 }
34 // Convenience methods. The S2LatLng must be normalized.
35 explicit S2Cell(S2Point const& p) { Init(S2CellId::FromPoint(p)); }
36 explicit S2Cell(S2LatLng const& ll) { Init(S2CellId::FromLatLng(ll)); }
37
38 inline S2CellId id() const { return id_; }
39 inline int face() const { return face_; }
40 inline int level() const { return level_; }
41 inline int orientation() const { return orientation_; }
42 inline bool is_leaf() const { return level_ == S2CellId::kMaxLevel; }
43
44 // These are equivalent to the S2CellId methods, but have a more efficient
45 // implementation since the level has been precomputed.
46 int GetSizeIJ() const;
47 double GetSizeST() const;
48
49 // Return the k-th vertex of the cell (k = 0,1,2,3). Vertices are returned
50 // in CCW order. The points returned by GetVertexRaw are not necessarily
51 // unit length.
52 S2Point GetVertex(int k) const { return GetVertexRaw(k).Normalize(); }
53 S2Point GetVertexRaw(int k) const;
54
55 // Return the inward-facing normal of the great circle passing through
56 // the edge from vertex k to vertex k+1 (mod 4). The normals returned
57 // by GetEdgeRaw are not necessarily unit length.
58 S2Point GetEdge(int k) const { return GetEdgeRaw(k).Normalize(); }
59 S2Point GetEdgeRaw(int k) const;
60
61 // If this is not a leaf cell, set children[0..3] to the four children of
62 // this cell (in traversal order) and return true. Otherwise returns false.
63 // This method is equivalent to the following:
64 //
65 // for (pos=0, id=child_begin(); id != child_end(); id = id.next(), ++pos)
66 // children[i] = S2Cell(id);
67 //
68 // except that it is more than two times faster.
69 bool Subdivide(S2Cell children[4]) const;
70
71 // Return the direction vector corresponding to the center in (s,t)-space of
72 // the given cell. This is the point at which the cell is divided into four
73 // subcells; it is not necessarily the centroid of the cell in (u,v)-space
74 // or (x,y,z)-space. The point returned by GetCenterRaw is not necessarily
75 // unit length.
76 S2Point GetCenter() const { return GetCenterRaw().Normalize(); }
77 S2Point GetCenterRaw() const;
78
79 // Return the average area for cells at the given level.
80 static double AverageArea(int level);
81
82 // Return the average area of cells at this level. This is accurate to
83 // within a factor of 1.7 (for S2_QUADRATIC_PROJECTION) and is extremely
84 // cheap to compute.
85 double AverageArea() const { return AverageArea(level_); }
86
87 // Return the approximate area of this cell. This method is accurate to
88 // within 3% percent for all cell sizes and accurate to within 0.1% for
89 // cells at level 5 or higher (i.e. squares 350km to a side or smaller
90 // on the Earth's surface). It is moderately cheap to compute.
91 double ApproxArea() const;
92
93 // Return the area of this cell as accurately as possible. This method is
94 // more expensive but it is accurate to 6 digits of precision even for leaf
95 // cells (whose area is approximately 1e-18).
96 double ExactArea() const;
97
98 ////////////////////////////////////////////////////////////////////////
99 // S2Region interface (see s2region.h for details):
100
101 virtual S2Cell* Clone() const;
102 virtual S2Cap GetCapBound() const;
103 virtual S2LatLngRect GetRectBound() const;
104 virtual bool Contains(S2Cell const& cell) const;
105 virtual bool MayIntersect(S2Cell const& cell) const;
106 virtual bool VirtualContainsPoint(S2Point const& p) const {
107 return Contains(p); // The same as Contains() below, just virtual.
108 }
109
110 // The point 'p' does not need to be normalized.
111 bool Contains(S2Point const& p) const;
112
113 virtual void Encode(Encoder* const encoder) const {
114 LOG(FATAL) << "Unimplemented";
115 }
116 virtual bool Decode(Decoder* const decoder) { return false; }
117
118 private:
119 // Internal method that does the actual work in the constructors.
120 void Init(S2CellId const& id);
121
122 // Return the latitude or longitude of the cell vertex given by (i,j),
123 // where "i" and "j" are either 0 or 1.
124 inline double GetLatitude(int i, int j) const;
125 inline double GetLongitude(int i, int j) const;
126
127 // This structure occupies 44 bytes plus one pointer for the vtable.
128 int8 face_;
129 int8 level_;
130 int8 orientation_;
131 S2CellId id_;
132 double uv_[2][2];
133};
134
135inline int S2Cell::GetSizeIJ() const {
136 return S2CellId::GetSizeIJ(level());
137}
138
139inline double S2Cell::GetSizeST() const {
140 return S2CellId::GetSizeST(level());
141}
142
143#endif // UTIL_GEOMETRY_S2CELL_H_
144