1 /* 2 * Copyright 2005 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.google.common.geometry; 17 18 public strictfp class S2LatLngRectTest extends GeometryTestCase { 19 testIntervalOps(S2LatLngRect x, S2LatLngRect y, String expectedRelation, S2LatLngRect expectedUnion, S2LatLngRect expectedIntersection)20 public void testIntervalOps(S2LatLngRect x, S2LatLngRect y, String expectedRelation, 21 S2LatLngRect expectedUnion, S2LatLngRect expectedIntersection) { 22 // Test all of the interval operations on the given pair of intervals. 23 // "expected_relation" is a sequence of "T" and "F" characters corresponding 24 // to the expected results of Contains(), InteriorContains(), Intersects(), 25 // and InteriorIntersects() respectively. 26 27 assertEquals(x.contains(y), expectedRelation.charAt(0) == 'T'); 28 assertEquals(x.interiorContains(y), expectedRelation.charAt(1) == 'T'); 29 assertEquals(x.intersects(y), expectedRelation.charAt(2) == 'T'); 30 assertEquals(x.interiorIntersects(y), expectedRelation.charAt(3) == 'T'); 31 32 assertEquals(x.contains(y), x.union(y).equals(x)); 33 assertEquals(x.intersects(y), !x.intersection(y).isEmpty()); 34 35 assertTrue(x.union(y).equals(expectedUnion)); 36 assertTrue(x.intersection(y).equals(expectedIntersection)); 37 38 if (y.getSize() == S2LatLng.fromRadians(0, 0)) { 39 S2LatLngRect r = x.addPoint(y.lo()); 40 assertTrue(r == expectedUnion); 41 } 42 } 43 testCellOps(S2LatLngRect r, S2Cell cell, int level)44 public void testCellOps(S2LatLngRect r, S2Cell cell, int level) { 45 // Test the relationship between the given rectangle and cell: 46 // 0 == no intersection, 1 == MayIntersect, 2 == Intersects, 47 // 3 == Vertex Containment, 4 == Contains 48 49 boolean vertexContained = false; 50 for (int i = 0; i < 4; ++i) { 51 if (r.contains(cell.getVertexRaw(i)) 52 || (!r.isEmpty() && cell.contains(r.getVertex(i).toPoint()))) { 53 vertexContained = true; 54 } 55 } 56 assertEquals(r.mayIntersect(cell), level >= 1); 57 assertEquals(r.intersects(cell), level >= 2); 58 assertEquals(vertexContained, level >= 3); 59 assertEquals(r.contains(cell), level >= 4); 60 } 61 testBasic()62 public void testBasic() { 63 // Most of the S2LatLngRect methods have trivial implementations that 64 // use the R1Interval and S1Interval classes, so most of the testing 65 // is done in those unit tests. 66 67 // Test basic properties of empty and full caps. 68 S2LatLngRect empty = S2LatLngRect.empty(); 69 S2LatLngRect full = S2LatLngRect.full(); 70 assertTrue(empty.isValid()); 71 assertTrue(empty.isEmpty()); 72 assertTrue(full.isValid()); 73 assertTrue(full.isFull()); 74 75 // assertTrue various constructors and accessor methods. 76 S2LatLngRect d1 = rectFromDegrees(-90, 0, -45, 180); 77 assertDoubleNear(d1.latLo().degrees(), -90); 78 assertDoubleNear(d1.latHi().degrees(), -45); 79 assertDoubleNear(d1.lngLo().degrees(), 0); 80 assertDoubleNear(d1.lngHi().degrees(), 180); 81 assertTrue(d1.lat().equals(new R1Interval(-S2.M_PI_2, -S2.M_PI_4))); 82 assertTrue(d1.lng().equals(new S1Interval(0, S2.M_PI))); 83 84 // FromCenterSize() 85 assertTrue( 86 S2LatLngRect.fromCenterSize(S2LatLng.fromDegrees(80, 170), S2LatLng.fromDegrees(40, 60)) 87 .approxEquals(rectFromDegrees(60, 140, 90, -160))); 88 assertTrue(S2LatLngRect 89 .fromCenterSize(S2LatLng.fromDegrees(10, 40), S2LatLng.fromDegrees(210, 400)).isFull()); 90 assertTrue( 91 S2LatLngRect.fromCenterSize(S2LatLng.fromDegrees(-90, 180), S2LatLng.fromDegrees(20, 50)) 92 .approxEquals(rectFromDegrees(-90, 155, -80, -155))); 93 94 // FromPoint(), FromPointPair() 95 assertEquals(S2LatLngRect.fromPoint(d1.lo()), new S2LatLngRect(d1.lo(), d1.lo())); 96 assertEquals( 97 S2LatLngRect.fromPointPair(S2LatLng.fromDegrees(-35, -140), S2LatLng.fromDegrees(15, 155)), 98 rectFromDegrees(-35, 155, 15, -140)); 99 assertEquals( 100 S2LatLngRect.fromPointPair(S2LatLng.fromDegrees(25, -70), S2LatLng.fromDegrees(-90, 80)), 101 rectFromDegrees(-90, -70, 25, 80)); 102 103 // GetCenter(), GetVertex(), Contains(S2LatLng), InteriorContains(S2LatLng). 104 S2LatLng eqM180 = S2LatLng.fromRadians(0, -S2.M_PI); 105 S2LatLng northPole = S2LatLng.fromRadians(S2.M_PI_2, 0); 106 S2LatLngRect r1 = new S2LatLngRect(eqM180, northPole); 107 108 assertEquals(r1.getCenter(), S2LatLng.fromRadians(S2.M_PI_4, -S2.M_PI_2)); 109 assertEquals(r1.getVertex(0), S2LatLng.fromRadians(0, S2.M_PI)); 110 assertEquals(r1.getVertex(1), S2LatLng.fromRadians(0, 0)); 111 assertEquals(r1.getVertex(2), S2LatLng.fromRadians(S2.M_PI_2, 0)); 112 assertEquals(r1.getVertex(3), S2LatLng.fromRadians(S2.M_PI_2, S2.M_PI)); 113 assertTrue(r1.contains(S2LatLng.fromDegrees(30, -45))); 114 assertTrue(!r1.contains(S2LatLng.fromDegrees(30, 45))); 115 assertTrue(!r1.interiorContains(eqM180) && !r1.interiorContains(northPole)); 116 assertTrue(r1.contains(new S2Point(0.5, -0.3, 0.1))); 117 assertTrue(!r1.contains(new S2Point(0.5, 0.2, 0.1))); 118 119 // Make sure that GetVertex() returns vertices in CCW order. 120 for (int i = 0; i < 4; ++i) { 121 double lat = S2.M_PI_4 * (i - 2); 122 double lng = S2.M_PI_2 * (i - 2) + 0.2; 123 S2LatLngRect r = new S2LatLngRect(new R1Interval(lat, lat + S2.M_PI_4), new S1Interval( 124 Math.IEEEremainder(lng, 2 * S2.M_PI), Math.IEEEremainder(lng + S2.M_PI_2, 2 * S2.M_PI))); 125 for (int k = 0; k < 4; ++k) { 126 assertTrue( 127 S2.simpleCCW(r.getVertex((k - 1) & 3).toPoint(), r.getVertex(k).toPoint(), 128 r.getVertex((k + 1) & 3).toPoint())); 129 } 130 } 131 132 // Contains(S2LatLngRect), InteriorContains(S2LatLngRect), 133 // Intersects(), InteriorIntersects(), Union(), Intersection(). 134 // 135 // Much more testing of these methods is done in s1interval_unittest 136 // and r1interval_unittest. 137 138 S2LatLngRect r1Mid = rectFromDegrees(45, -90, 45, -90); 139 S2LatLngRect reqM180 = new S2LatLngRect(eqM180, eqM180); 140 S2LatLngRect rNorthPole = new S2LatLngRect(northPole, northPole); 141 142 testIntervalOps(r1, r1Mid, "TTTT", r1, r1Mid); 143 testIntervalOps(r1, reqM180, "TFTF", r1, reqM180); 144 testIntervalOps(r1, rNorthPole, "TFTF", r1, rNorthPole); 145 146 assertTrue(r1.equals(rectFromDegrees(0, -180, 90, 0))); 147 testIntervalOps(r1, rectFromDegrees(-10, -1, 1, 20), "FFTT", rectFromDegrees(-10, -180, 90, 20), 148 rectFromDegrees(0, -1, 1, 0)); 149 testIntervalOps(r1, rectFromDegrees(-10, -1, 0, 20), "FFTF", rectFromDegrees(-10, -180, 90, 20), 150 rectFromDegrees(0, -1, 0, 0)); 151 testIntervalOps(r1, rectFromDegrees(-10, 0, 1, 20), "FFTF", rectFromDegrees(-10, -180, 90, 20), 152 rectFromDegrees(0, 0, 1, 0)); 153 154 testIntervalOps(rectFromDegrees(-15, -160, -15, -150), rectFromDegrees(20, 145, 25, 155), 155 "FFFF", rectFromDegrees(-15, 145, 25, -150), empty); 156 testIntervalOps(rectFromDegrees(70, -10, 90, -140), rectFromDegrees(60, 175, 80, 5), "FFTT", 157 rectFromDegrees(60, -180, 90, 180), rectFromDegrees(70, 175, 80, 5)); 158 159 // assertTrue that the intersection of two rectangles that overlap in 160 // latitude 161 // but not longitude is valid, and vice versa. 162 testIntervalOps(rectFromDegrees(12, 30, 60, 60), rectFromDegrees(0, 0, 30, 18), "FFFF", 163 rectFromDegrees(0, 0, 60, 60), empty); 164 testIntervalOps(rectFromDegrees(0, 0, 18, 42), rectFromDegrees(30, 12, 42, 60), "FFFF", 165 rectFromDegrees(0, 0, 42, 60), empty); 166 167 // AddPoint() 168 S2LatLngRect p = S2LatLngRect.empty(); 169 p = p.addPoint(S2LatLng.fromDegrees(0, 0)); 170 p = p.addPoint(S2LatLng.fromRadians(0, -S2.M_PI_2)); 171 p = p.addPoint(S2LatLng.fromRadians(S2.M_PI_4, -S2.M_PI)); 172 p = p.addPoint(new S2Point(0, 0, 1)); 173 assertTrue(p.equals(r1)); 174 175 // Expanded() 176 assertTrue( 177 rectFromDegrees(70, 150, 80, 170).expanded(S2LatLng.fromDegrees(20, 30)).approxEquals( 178 rectFromDegrees(50, 120, 90, -160))); 179 assertTrue(S2LatLngRect.empty().expanded(S2LatLng.fromDegrees(20, 30)).isEmpty()); 180 assertTrue(S2LatLngRect.full().expanded(S2LatLng.fromDegrees(20, 30)).isFull()); 181 assertTrue( 182 rectFromDegrees(-90, 170, 10, 20).expanded(S2LatLng.fromDegrees(30, 80)).approxEquals( 183 rectFromDegrees(-90, -180, 40, 180))); 184 185 // ConvolveWithCap() 186 S2LatLngRect llr1 = 187 new S2LatLngRect(S2LatLng.fromDegrees(0, 170), S2LatLng.fromDegrees(0, -170)) 188 .convolveWithCap(S1Angle.degrees(15)); 189 S2LatLngRect llr2 = 190 new S2LatLngRect(S2LatLng.fromDegrees(-15, 155), S2LatLng.fromDegrees(15, -155)); 191 assertTrue(llr1.approxEquals(llr2)); 192 193 llr1 = new S2LatLngRect(S2LatLng.fromDegrees(60, 150), S2LatLng.fromDegrees(80, 10)) 194 .convolveWithCap(S1Angle.degrees(15)); 195 llr2 = new S2LatLngRect(S2LatLng.fromDegrees(45, -180), S2LatLng.fromDegrees(90, 180)); 196 assertTrue(llr1.approxEquals(llr2)); 197 198 // GetCapBound(), bounding cap at center is smaller: 199 assertTrue(new S2LatLngRect(S2LatLng.fromDegrees(-45, -45), S2LatLng.fromDegrees(45, 45)) 200 .getCapBound().approxEquals(S2Cap.fromAxisHeight(new S2Point(1, 0, 0), 0.5))); 201 // GetCapBound(), bounding cap at north pole is smaller: 202 assertTrue(new S2LatLngRect(S2LatLng.fromDegrees(88, -80), S2LatLng.fromDegrees(89, 80)) 203 .getCapBound().approxEquals(S2Cap.fromAxisAngle(new S2Point(0, 0, 1), S1Angle.degrees(2)))); 204 // GetCapBound(), longitude span > 180 degrees: 205 assertTrue( 206 new S2LatLngRect(S2LatLng.fromDegrees(-30, -150), S2LatLng.fromDegrees(-10, 50)) 207 .getCapBound() 208 .approxEquals(S2Cap.fromAxisAngle(new S2Point(0, 0, -1), S1Angle.degrees(80)))); 209 210 // Contains(S2Cell), MayIntersect(S2Cell), Intersects(S2Cell) 211 212 // Special cases. 213 testCellOps(empty, S2Cell.fromFacePosLevel(3, (byte) 0, 0), 0); 214 testCellOps(full, S2Cell.fromFacePosLevel(2, (byte) 0, 0), 4); 215 testCellOps(full, S2Cell.fromFacePosLevel(5, (byte) 0, 25), 4); 216 217 // This rectangle includes the first quadrant of face 0. It's expanded 218 // slightly because cell bounding rectangles are slightly conservative. 219 S2LatLngRect r4 = rectFromDegrees(-45.1, -45.1, 0.1, 0.1); 220 testCellOps(r4, S2Cell.fromFacePosLevel(0, (byte) 0, 0), 3); 221 testCellOps(r4, S2Cell.fromFacePosLevel(0, (byte) 0, 1), 4); 222 testCellOps(r4, S2Cell.fromFacePosLevel(1, (byte) 0, 1), 0); 223 224 // This rectangle intersects the first quadrant of face 0. 225 S2LatLngRect r5 = rectFromDegrees(-10, -45, 10, 0); 226 testCellOps(r5, S2Cell.fromFacePosLevel(0, (byte) 0, 0), 3); 227 testCellOps(r5, S2Cell.fromFacePosLevel(0, (byte) 0, 1), 3); 228 testCellOps(r5, S2Cell.fromFacePosLevel(1, (byte) 0, 1), 0); 229 230 // Rectangle consisting of a single point. 231 testCellOps(rectFromDegrees(4, 4, 4, 4), S2Cell.fromFacePosLevel(0, (byte) 0, 0), 3); 232 233 // Rectangles that intersect the bounding rectangle of a face 234 // but not the face itself. 235 testCellOps(rectFromDegrees(41, -87, 42, -79), S2Cell.fromFacePosLevel(2, (byte) 0, 0), 1); 236 testCellOps(rectFromDegrees(-41, 160, -40, -160), S2Cell.fromFacePosLevel(5, (byte) 0, 0), 1); 237 { 238 // This is the leaf cell at the top right hand corner of face 0. 239 // It has two angles of 60 degrees and two of 120 degrees. 240 S2Cell cell0tr = new S2Cell(new S2Point(1 + 1e-12, 1, 1)); 241 S2LatLngRect bound0tr = cell0tr.getRectBound(); 242 S2LatLng v0 = new S2LatLng(cell0tr.getVertexRaw(0)); 243 testCellOps( 244 rectFromDegrees(v0.lat().degrees() - 1e-8, v0.lng().degrees() - 1e-8, 245 v0.lat().degrees() - 2e-10, v0.lng().degrees() + 1e-10), cell0tr, 1); 246 } 247 248 // Rectangles that intersect a face but where no vertex of one region 249 // is contained by the other region. The first one passes through 250 // a corner of one of the face cells. 251 testCellOps(rectFromDegrees(-37, -70, -36, -20), S2Cell.fromFacePosLevel(5, (byte) 0, 0), 2); 252 { 253 // These two intersect like a diamond and a square. 254 S2Cell cell202 = S2Cell.fromFacePosLevel(2, (byte) 0, 2); 255 S2LatLngRect bound202 = cell202.getRectBound(); 256 testCellOps( 257 rectFromDegrees(bound202.lo().lat().degrees() + 3, bound202.lo().lng().degrees() + 3, 258 bound202.hi().lat().degrees() - 3, bound202.hi().lng().degrees() - 3), cell202, 2); 259 } 260 } 261 testArea()262 public void testArea() { 263 assertEquals(0.0, S2LatLngRect.empty().area()); 264 assertDoubleNear(4 * Math.PI, S2LatLngRect.full().area()); 265 assertDoubleNear(Math.PI / 2, rectFromDegrees(0, 0, 90, 90).area()); 266 } 267 testEdgeBound()268 public void testEdgeBound() { 269 // assertTrue cases where min/max latitude is not at a vertex. 270 assertDoubleNear(getEdgeBound(1, 1, 1, 1, -1, 1).lat().hi(), S2.M_PI_4); // Max, 271 // CW 272 assertDoubleNear(getEdgeBound(1, -1, 1, 1, 1, 1).lat().hi(), S2.M_PI_4); // Max, 273 // CCW 274 assertDoubleNear(getEdgeBound(1, -1, -1, -1, -1, -1).lat().lo(), -S2.M_PI_4); // Min, 275 // CW 276 assertDoubleNear(getEdgeBound(-1, 1, -1, -1, -1, -1).lat().lo(), -S2.M_PI_4); // Min, 277 // CCW 278 279 // assertTrue cases where the edge passes through one of the poles. 280 assertDoubleNear(getEdgeBound(.3, .4, 1, -.3, -.4, 1).lat().hi(), S2.M_PI_2); 281 assertDoubleNear(getEdgeBound(.3, .4, -1, -.3, -.4, -1).lat().lo(), -S2.M_PI_2); 282 283 // assertTrue cases where the min/max latitude is attained at a vertex. 284 final double kCubeLat = Math.asin(Math.sqrt(1. / 3)); // 35.26 degrees 285 assertTrue( 286 getEdgeBound(1, 1, 1, 1, -1, -1).lat().approxEquals(new R1Interval(-kCubeLat, kCubeLat))); 287 assertTrue( 288 getEdgeBound(1, -1, 1, 1, 1, -1).lat().approxEquals(new R1Interval(-kCubeLat, kCubeLat))); 289 } 290 testGetDistanceOverlapping()291 public void testGetDistanceOverlapping() { 292 // Check pairs of rectangles that overlap: (should all return 0): 293 S2LatLngRect a = rectFromDegrees(0, 0, 2, 2); 294 S2LatLngRect b = pointRectFromDegrees(0, 0); 295 S1Angle zero = S1Angle.radians(0); 296 assertEquals(zero, a.getDistance(a)); 297 assertEquals(zero, a.getDistance(b)); 298 assertEquals(zero, b.getDistance(b)); 299 assertEquals(zero, a.getDistance(S2LatLng.fromDegrees(0, 0))); 300 assertEquals(zero, a.getDistance(rectFromDegrees(0, 1, 2, 3))); 301 assertEquals(zero, a.getDistance(rectFromDegrees(0, 2, 2, 4))); 302 assertEquals(zero, a.getDistance(rectFromDegrees(1, 0, 3, 2))); 303 assertEquals(zero, a.getDistance(rectFromDegrees(2, 0, 4, 2))); 304 assertEquals(zero, a.getDistance(rectFromDegrees(1, 1, 3, 3))); 305 assertEquals(zero, a.getDistance(rectFromDegrees(2, 2, 4, 4))); 306 } 307 testGetDistanceRectVsPoint()308 public void testGetDistanceRectVsPoint() { 309 // Rect that spans 180. 310 S2LatLngRect a = rectFromDegrees(-1, -1, 2, 1); 311 verifyGetDistance(a, pointRectFromDegrees(-2, -1)); 312 verifyGetDistance(a, pointRectFromDegrees(1, 2)); 313 314 verifyGetDistance(pointRectFromDegrees(-2, -1), a); 315 verifyGetDistance(pointRectFromDegrees(1, 2), a); 316 317 verifyGetRectPointDistance(a, S2LatLng.fromDegrees(-2, -1)); 318 verifyGetRectPointDistance(a, S2LatLng.fromDegrees(1, 2)); 319 320 // Tests near the north pole. 321 S2LatLngRect b = rectFromDegrees(86, 0, 88, 2); 322 verifyGetDistance(b, pointRectFromDegrees(87, 3)); 323 verifyGetDistance(b, pointRectFromDegrees(87, -1)); 324 verifyGetDistance(b, pointRectFromDegrees(89, 1)); 325 verifyGetDistance(b, pointRectFromDegrees(89, 181)); 326 verifyGetDistance(b, pointRectFromDegrees(85, 1)); 327 verifyGetDistance(b, pointRectFromDegrees(85, 181)); 328 verifyGetDistance(b, pointRectFromDegrees(90, 0)); 329 330 verifyGetDistance(pointRectFromDegrees(87, 3), b); 331 verifyGetDistance(pointRectFromDegrees(87, -1), b); 332 verifyGetDistance(pointRectFromDegrees(89, 1), b); 333 verifyGetDistance(pointRectFromDegrees(89, 181), b); 334 verifyGetDistance(pointRectFromDegrees(85, 1), b); 335 verifyGetDistance(pointRectFromDegrees(85, 181), b); 336 verifyGetDistance(pointRectFromDegrees(90, 0), b); 337 338 verifyGetRectPointDistance(b, S2LatLng.fromDegrees(87, 3)); 339 verifyGetRectPointDistance(b, S2LatLng.fromDegrees(87, -1)); 340 verifyGetRectPointDistance(b, S2LatLng.fromDegrees(89, 1)); 341 verifyGetRectPointDistance(b, S2LatLng.fromDegrees(89, 181)); 342 verifyGetRectPointDistance(b, S2LatLng.fromDegrees(85, 1)); 343 verifyGetRectPointDistance(b, S2LatLng.fromDegrees(85, 181)); 344 verifyGetRectPointDistance(b, S2LatLng.fromDegrees(90, 0)); 345 346 // Rect that touches the north pole. 347 S2LatLngRect c = rectFromDegrees(88, 0, 90, 2); 348 verifyGetDistance(c, pointRectFromDegrees(89, 3)); 349 verifyGetDistance(c, pointRectFromDegrees(89, 90)); 350 verifyGetDistance(c, pointRectFromDegrees(89, 181)); 351 verifyGetDistance(pointRectFromDegrees(89, 3), c); 352 verifyGetDistance(pointRectFromDegrees(89, 90), c); 353 verifyGetDistance(pointRectFromDegrees(89, 181), c); 354 } 355 testGetDistanceRectVsRect()356 public void testGetDistanceRectVsRect() { 357 // Rect that spans 180. 358 S2LatLngRect a = rectFromDegrees(-1, -1, 2, 1); 359 verifyGetDistance(a, rectFromDegrees(0, 2, 1, 3)); 360 verifyGetDistance(a, rectFromDegrees(-2, -3, -1, -2)); 361 362 // Tests near the south pole. 363 S2LatLngRect b = rectFromDegrees(-87, 0, -85, 3); 364 verifyGetDistance(b, rectFromDegrees(-89, 1, -88, 2)); 365 verifyGetDistance(b, rectFromDegrees(-84, 1, -83, 2)); 366 verifyGetDistance(b, rectFromDegrees(-88, 90, -86, 91)); 367 verifyGetDistance(b, rectFromDegrees(-84, -91, -83, -90)); 368 verifyGetDistance(b, rectFromDegrees(-90, 181, -89, 182)); 369 verifyGetDistance(b, rectFromDegrees(-84, 181, -83, 182)); 370 } 371 testGetDistanceRandomPairs()372 public void testGetDistanceRandomPairs() { 373 // Test random pairs. 374 for (int i = 0; i < 10000; ++i) { 375 S2LatLngRect a = 376 S2LatLngRect.fromPointPair(new S2LatLng(randomPoint()), new S2LatLng(randomPoint())); 377 S2LatLngRect b = 378 S2LatLngRect.fromPointPair(new S2LatLng(randomPoint()), new S2LatLng(randomPoint())); 379 verifyGetDistance(a, b); 380 381 382 S2LatLng c = new S2LatLng(randomPoint()); 383 verifyGetRectPointDistance(a, c); 384 verifyGetRectPointDistance(b, c); 385 } 386 } 387 bruteForceDistance(S2LatLngRect a, S2LatLngRect b)388 private static S1Angle bruteForceDistance(S2LatLngRect a, S2LatLngRect b) { 389 if (a.intersects(b)) { 390 return S1Angle.radians(0); 391 } 392 393 // Compare every point in 'a' against every latitude edge and longitude edge 394 // in 'b', and vice-versa, for a total of 16 point-vs-latitude-edge tests 395 // and 16 point-vs-longitude-edge tests. 396 S2LatLng pntA[] = 397 {new S2LatLng(a.latLo(), a.lngLo()), new S2LatLng(a.latLo(), a.lngHi()), 398 new S2LatLng(a.latHi(), a.lngHi()), new S2LatLng(a.latHi(), a.lngLo())}; 399 S2LatLng pntB[] = 400 {new S2LatLng(b.latLo(), b.lngLo()), new S2LatLng(b.latLo(), b.lngHi()), 401 new S2LatLng(b.latHi(), b.lngHi()), new S2LatLng(b.latHi(), b.lngLo())}; 402 403 // Make arrays containing the lo/hi latitudes and the lo/hi longitude edges. 404 S1Angle latA[] = {a.latLo(), a.latHi()}; 405 S1Angle latB[] = {b.latLo(), b.latHi()}; 406 S2Point lng_edge_a[][] = 407 { {pntA[0].toPoint(), pntA[3].toPoint()}, {pntA[1].toPoint(), pntA[2].toPoint()}}; 408 S2Point lng_edge_b[][] = 409 { {pntB[0].toPoint(), pntB[3].toPoint()}, {pntB[1].toPoint(), pntB[2].toPoint()}}; 410 411 S1Angle minDistance = S1Angle.degrees(180.0); 412 for (int i = 0; i < 4; ++i) { 413 // For each point in a and b. 414 S2LatLng currentA = pntA[i]; 415 S2LatLng currentB = pntB[i]; 416 417 for (int j = 0; j < 2; ++j) { 418 // Get distances to latitude and longitude edges. 419 S1Angle aToLat = getDistance(currentA, latB[j], b.lng()); 420 S1Angle bToLat = getDistance(currentB, latA[j], a.lng()); 421 S1Angle aToLng = 422 S2EdgeUtil.getDistance(currentA.toPoint(), lng_edge_b[j][0], lng_edge_b[j][1]); 423 S1Angle bToLng = 424 S2EdgeUtil.getDistance(currentB.toPoint(), lng_edge_a[j][0], lng_edge_a[j][1]); 425 426 minDistance = S1Angle.min( 427 minDistance, S1Angle.min(aToLat, S1Angle.min(bToLat, S1Angle.min(aToLng, bToLng)))); 428 } 429 } 430 return minDistance; 431 } 432 bruteForceRectPointDistance(S2LatLngRect a, S2LatLng b)433 private static S1Angle bruteForceRectPointDistance(S2LatLngRect a, S2LatLng b) { 434 if (a.contains(b)) { 435 return S1Angle.radians(0); 436 } 437 438 S1Angle bToLoLat = getDistance(b, a.latLo(), a.lng()); 439 S1Angle bToHiLat = getDistance(b, a.latHi(), a.lng()); 440 S1Angle bToLoLng = 441 S2EdgeUtil.getDistance(b.toPoint(), new S2LatLng(a.latLo(), a.lngLo()).toPoint(), 442 new S2LatLng(a.latHi(), a.lngLo()).toPoint()); 443 S1Angle bToHiLng = 444 S2EdgeUtil.getDistance(b.toPoint(), new S2LatLng(a.latLo(), a.lngHi()).toPoint(), 445 new S2LatLng(a.latHi(), a.lngHi()).toPoint()); 446 return S1Angle.min(bToLoLat, S1Angle.min(bToHiLat, S1Angle.min(bToLoLng, bToHiLng))); 447 } 448 449 /** 450 * Returns the minimum distance from X to the latitude line segment defined by 451 * the given latitude and longitude interval. 452 */ getDistance(S2LatLng x, S1Angle lat, S1Interval interval)453 private static S1Angle getDistance(S2LatLng x, S1Angle lat, S1Interval interval) { 454 assertTrue(x.isValid()); 455 assertTrue(interval.isValid()); 456 457 // Is X inside the longitude interval? 458 if (interval.contains(x.lng().radians())) 459 return S1Angle.radians(Math.abs(x.lat().radians() - lat.radians())); 460 461 // Return the distance to the closer endpoint. 462 return S1Angle.min(x.getDistance(new S2LatLng(lat, S1Angle.radians(interval.lo()))), 463 x.getDistance(new S2LatLng(lat, S1Angle.radians(interval.hi())))); 464 } 465 getEdgeBound(double x1, double y1, double z1, double x2, double y2, double z2)466 private static S2LatLngRect getEdgeBound(double x1, 467 double y1, 468 double z1, 469 double x2, 470 double y2, 471 double z2) { 472 return S2LatLngRect.fromEdge( 473 S2Point.normalize(new S2Point(x1, y1, z1)), S2Point.normalize(new S2Point(x2, y2, z2))); 474 } 475 pointRectFromDegrees(double lat, double lng)476 private static S2LatLngRect pointRectFromDegrees(double lat, double lng) { 477 return S2LatLngRect.fromPoint(S2LatLng.fromDegrees(lat, lng).normalized()); 478 } 479 rectFromDegrees( double latLo, double lngLo, double latHi, double lngHi)480 private static S2LatLngRect rectFromDegrees( 481 double latLo, double lngLo, double latHi, double lngHi) { 482 // Convenience method to construct a rectangle. This method is 483 // intentionally *not* in the S2LatLngRect interface because the 484 // argument order is ambiguous, but hopefully it's not too confusing 485 // within the context of this unit test. 486 487 return new S2LatLngRect(S2LatLng.fromDegrees(latLo, lngLo).normalized(), 488 S2LatLng.fromDegrees(latHi, lngHi).normalized()); 489 } 490 491 /** 492 * This method verifies a.getDistance(b), where b is a S2LatLng, by comparing 493 * its result against a.getDistance(c), c being the point rectangle created 494 * from b. 495 */ verifyGetRectPointDistance(S2LatLngRect a, S2LatLng p)496 private static void verifyGetRectPointDistance(S2LatLngRect a, S2LatLng p) { 497 S1Angle distance1 = bruteForceRectPointDistance(a, p.normalized()); 498 S1Angle distance2 = a.getDistance(p.normalized()); 499 assertEquals(distance1.radians(), distance2.radians(), 1e-10); 500 } 501 502 /** 503 * This method verifies a.getDistance(b) by comparing its result against a 504 * brute-force implementation. The correctness of the brute-force version is 505 * much easier to verify by inspection. 506 */ verifyGetDistance(S2LatLngRect a, S2LatLngRect b)507 private static void verifyGetDistance(S2LatLngRect a, S2LatLngRect b) { 508 S1Angle distance1 = bruteForceDistance(a, b); 509 S1Angle distance2 = a.getDistance(b); 510 assertEquals(distance1.radians(), distance2.radians(), 1e-10); 511 } 512 } 513