1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2CELLUNION_H_
4#define UTIL_GEOMETRY_S2CELLUNION_H_
5
6#include <vector>
7using std::vector;
8
9#include "base/integral_types.h"
10#include "base/logging.h"
11#include "base/macros.h"
12#include "s2region.h"
13#include "s2cellid.h"
14
15class S1Angle;
16class S2Cell;
17
18// An S2CellUnion is a region consisting of cells of various sizes. Typically
19// a cell union is used to approximate some other shape. There is a tradeoff
20// between the accuracy of the approximation and how many cells are used.
21// Unlike polygons, cells have a fixed hierarchical structure. This makes
22// them more suitable for optimizations based on preprocessing.
23class S2CellUnion : public S2Region {
24 public:
25 // The default constructor does nothing. The cell union cannot be used
26 // until one of the Init() methods is called.
27 S2CellUnion() {}
28
29 // Populates a cell union with the given S2CellIds or 64-bit cells ids, and
30 // then calls Normalize(). The InitSwap() version takes ownership of the
31 // vector data without copying and clears the given vector. These methods
32 // may be called multiple times.
33 void Init(vector<S2CellId> const& cell_ids);
34 void Init(vector<uint64> const& cell_ids);
35 void InitSwap(vector<S2CellId>* cell_ids);
36
37 // Like Init(), but does not call Normalize(). The cell union *must* be
38 // normalized before doing any calculations with it, so it is the caller's
39 // responsibility to make sure that the input is normalized. This method is
40 // useful when converting cell unions to another representation and back.
41 // These methods may be called multiple times.
42 void InitRaw(vector<S2CellId> const& cell_ids);
43 void InitRaw(vector<uint64> const& cell_ids);
44 void InitRawSwap(vector<S2CellId>* cell_ids);
45
46 // Gives ownership of the vector data to the client without copying, and
47 // clears the content of the cell union. The original data in cell_ids
48 // is lost if there was any. This is the opposite of InitRawSwap().
49 void Detach(vector<S2CellId>* cell_ids);
50
51 // Convenience methods for accessing the individual cell ids.
52 int num_cells() const { return cell_ids_.size(); }
53 S2CellId const& cell_id(int i) const { return cell_ids_[i]; }
54
55 // Direct access to the underlying vector for STL algorithms.
56 vector<S2CellId> const& cell_ids() const { return cell_ids_; }
57
58 // Normalizes the cell union by discarding cells that are contained by other
59 // cells, replacing groups of 4 child cells by their parent cell whenever
60 // possible, and sorting all the cell ids in increasing order. Returns true
61 // if the number of cells was reduced.
62 //
63 // This method *must* be called before doing any calculations on the cell
64 // union, such as Intersects() or Contains().
65 bool Normalize();
66
67 // Replaces "output" with an expanded version of the cell union where any
68 // cells whose level is less than "min_level" or where (level - min_level)
69 // is not a multiple of "level_mod" are replaced by their children, until
70 // either both of these conditions are satisfied or the maximum level is
71 // reached.
72 //
73 // This method allows a covering generated by S2RegionCoverer using
74 // min_level() or level_mod() constraints to be stored as a normalized cell
75 // union (which allows various geometric computations to be done) and then
76 // converted back to the original list of cell ids that satisfies the
77 // desired constraints.
78 void Denormalize(int min_level, int level_mod,
79 vector<S2CellId>* output) const;
80
81 // If there are more than "excess" elements of the cell_ids() vector that
82 // are allocated but unused, reallocate the array to eliminate the excess
83 // space. This reduces memory usage when many cell unions need to be held
84 // in memory at once.
85 void Pack(int excess = 0);
86
87 // Return true if the cell union contains the given cell id. Containment is
88 // defined with respect to regions, e.g. a cell contains its 4 children.
89 // This is a fast operation (logarithmic in the size of the cell union).
90 bool Contains(S2CellId const& id) const;
91
92 // Return true if the cell union intersects the given cell id.
93 // This is a fast operation (logarithmic in the size of the cell union).
94 bool Intersects(S2CellId const& id) const;
95
96 // Return true if this cell union contain/intersects the given other cell
97 // union.
98 bool Contains(S2CellUnion const* y) const;
99 bool Intersects(S2CellUnion const* y) const;
100
101 // Initialize this cell union to the union, intersection, or
102 // difference (x - y) of the two given cell unions.
103 // Requires: x != this and y != this.
104 void GetUnion(S2CellUnion const* x, S2CellUnion const* y);
105 void GetIntersection(S2CellUnion const* x, S2CellUnion const* y);
106 void GetDifference(S2CellUnion const* x, S2CellUnion const* y);
107
108 // Specialized version of GetIntersection() that gets the intersection of a
109 // cell union with the given cell id. This can be useful for "splitting" a
110 // cell union into chunks.
111 void GetIntersection(S2CellUnion const* x, S2CellId const& id);
112
113 // Expands the cell union by adding a "rim" of cells on expand_level
114 // around the union boundary.
115 //
116 // For each cell c in the union, we add all cells at level
117 // expand_level that abut c. There are typically eight of those
118 // (four edge-abutting and four sharing a vertex). However, if c is
119 // finer than expand_level, we add all cells abutting
120 // c.parent(expand_level) as well as c.parent(expand_level) itself,
121 // as an expand_level cell rarely abuts a smaller cell.
122 //
123 // Note that the size of the output is exponential in
124 // "expand_level". For example, if expand_level == 20 and the input
125 // has a cell at level 10, there will be on the order of 4000
126 // adjacent cells in the output. For most applications the
127 // Expand(min_radius, max_level_diff) method below is easier to use.
128 void Expand(int expand_level);
129
130 // Expand the cell union such that it contains all points whose distance to
131 // the cell union is at most "min_radius", but do not use cells that are
132 // more than "max_level_diff" levels higher than the largest cell in the
133 // input. The second parameter controls the tradeoff between accuracy and
134 // output size when a large region is being expanded by a small amount
135 // (e.g. expanding Canada by 1km). For example, if max_level_diff == 4 the
136 // region will always be expanded by approximately 1/16 the width of its
137 // largest cell. Note that in the worst case, the number of cells in the
138 // output can be up to 4 * (1 + 2 ** max_level_diff) times larger than the
139 // number of cells in the input.
140 void Expand(S1Angle const& min_radius, int max_level_diff);
141
142 // Create a cell union that corresponds to a continuous range of cell ids.
143 // The output is a normalized collection of cell ids that covers the leaf
144 // cells between "min_id" and "max_id" inclusive.
145 // Requires: min_id.is_leaf(), max_id.is_leaf(), min_id <= max_id.
146 void InitFromRange(S2CellId const& min_id, S2CellId const& max_id);
147
148 // The number of leaf cells covered by the union.
149 // This will be no more than 6*2^60 for the whole sphere.
150 uint64 LeafCellsCovered() const;
151
152 // Approximate this cell union's area by summing the average area of
153 // each contained cell's average area, using the AverageArea method
154 // from the S2Cell class.
155 // This is equivalent to the number of leaves covered, multiplied by
156 // the average area of a leaf.
157 // Note that AverageArea does not take into account distortion of cell, and
158 // thus may be off by up to a factor of 1.7.
159 // NOTE: Since this is proportional to LeafCellsCovered(), it is
160 // always better to use the other function if all you care about is
161 // the relative average area between objects.
162 double AverageBasedArea() const;
163
164 // Calculates this cell union's area by summing the approximate area for each
165 // contained cell, using the ApproxArea method from the S2Cell class.
166 double ApproxArea() const;
167
168 // Calculates this cell union's area by summing the exact area for each
169 // contained cell, using the Exact method from the S2Cell class.
170 double ExactArea() const;
171
172 ////////////////////////////////////////////////////////////////////////
173 // S2Region interface (see s2region.h for details):
174
175 virtual S2CellUnion* Clone() const;
176 virtual S2Cap GetCapBound() const;
177 virtual S2LatLngRect GetRectBound() const;
178
179 // This is a fast operation (logarithmic in the size of the cell union).
180 virtual bool Contains(S2Cell const& cell) const;
181
182 // This is a fast operation (logarithmic in the size of the cell union).
183 virtual bool MayIntersect(S2Cell const& cell) const;
184
185 virtual bool VirtualContainsPoint(S2Point const& p) const {
186 return Contains(p); // The same as Contains() below, just virtual.
187 }
188
189 virtual void Encode(Encoder* const encoder) const {
190 LOG(FATAL) << "Unimplemented";
191 }
192 virtual bool Decode(Decoder* const decoder) { return false; }
193
194 // The point 'p' does not need to be normalized.
195 // This is a fast operation (logarithmic in the size of the cell union).
196 bool Contains(S2Point const& p) const;
197
198 private:
199 vector<S2CellId> cell_ids_;
200
201 DISALLOW_EVIL_CONSTRUCTORS(S2CellUnion);
202};
203
204// Return true if two cell unions are identical.
205bool operator==(S2CellUnion const& x, S2CellUnion const& y);
206
207#endif // UTIL_GEOMETRY_S2CELLUNION_H_
208