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