| 161 | } // namespace |
| 162 | |
| 163 | GlobeRectangle S2CellID::computeBoundingRectangle() const { |
| 164 | GoogleS2CellID google(this->_id); |
| 165 | R2Rect uv_ = google.GetBoundUV(); |
| 166 | int level_ = google.level(); |
| 167 | int face_ = google.face(); |
| 168 | |
| 169 | // The below code is copied from s2geometry's s2cell.cc. |
| 170 | // We copy it rather than just call it like we do with other code in that |
| 171 | // library because s2cell.cc has some steep dependencies that eventually lead |
| 172 | // to requiring OpenSSL. |
| 173 | |
| 174 | // However, we've changed the implementation slightly from s2geometry. In |
| 175 | // s2geometry, a cell that contains the North or South pole is deemed to |
| 176 | // include all longitudes. While this is technically true, because any |
| 177 | // longitude at +/-PI/2 radians latitude is at the pole, it is still |
| 178 | // "losing information" to present it that way. We'd rather return the |
| 179 | // actual longitude bounds and let client code account for the singularity |
| 180 | // when necessary. So we don't do the "PolarClosure" operation performed by |
| 181 | // the original implementation. |
| 182 | |
| 183 | if (level_ > 0) { |
| 184 | // Except for cells at level 0, the latitude and longitude extremes are |
| 185 | // attained at the vertices. Furthermore, the latitude range is |
| 186 | // determined by one pair of diagonally opposite vertices and the |
| 187 | // longitude range is determined by the other pair. |
| 188 | // |
| 189 | // We first determine which corner (i,j) of the cell has the largest |
| 190 | // absolute latitude. To maximize latitude, we want to find the point in |
| 191 | // the cell that has the largest absolute z-coordinate and the smallest |
| 192 | // absolute x- and y-coordinates. To do this we look at each coordinate |
| 193 | // (u and v), and determine whether we want to minimize or maximize that |
| 194 | // coordinate based on the axis direction and the cell's (u,v) quadrant. |
| 195 | double u = uv_[0][0] + uv_[0][1]; |
| 196 | double v = uv_[1][0] + uv_[1][1]; |
| 197 | int i = S2::GetUAxis(face_)[2] == 0 ? (u < 0) : (u > 0); |
| 198 | int j = S2::GetVAxis(face_)[2] == 0 ? (v < 0) : (v > 0); |
| 199 | R1Interval lat = R1Interval::FromPointPair( |
| 200 | GetLatitude(uv_, face_, i, j), |
| 201 | GetLatitude(uv_, face_, 1 - i, 1 - j)); |
| 202 | S1Interval lng = S1Interval::FromPointPair( |
| 203 | GetLongitude(uv_, face_, i, 1 - j), |
| 204 | GetLongitude(uv_, face_, 1 - i, j)); |
| 205 | |
| 206 | // We grow the bounds slightly to make sure that the bounding rectangle |
| 207 | // contains S2LatLng(P) for any point P inside the loop L defined by the |
| 208 | // four *normalized* vertices. Note that normalization of a vector can |
| 209 | // change its direction by up to 0.5 * DBL_EPSILON radians, and it is not |
| 210 | // enough just to add Normalize() calls to the code above because the |
| 211 | // latitude/longitude ranges are not necessarily determined by diagonally |
| 212 | // opposite vertex pairs after normalization. |
| 213 | // |
| 214 | // We would like to bound the amount by which the latitude/longitude of a |
| 215 | // contained point P can exceed the bounds computed above. In the case of |
| 216 | // longitude, the normalization error can change the direction of rounding |
| 217 | // leading to a maximum difference in longitude of 2 * DBL_EPSILON. In |
| 218 | // the case of latitude, the normalization error can shift the latitude by |
| 219 | // up to 0.5 * DBL_EPSILON and the other sources of error can cause the |
| 220 | // two latitudes to differ by up to another 1.5 * DBL_EPSILON, which also |
no test coverage detected