1 /* 2 * Copyright 2006 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 17 package com.google.common.geometry; 18 19 import com.google.common.collect.Lists; 20 import com.google.common.collect.Maps; 21 import com.google.common.collect.Sets; 22 23 import java.util.List; 24 import java.util.Map; 25 import java.util.Set; 26 import java.util.logging.Logger; 27 28 /** 29 * Tests for {@link S2Loop}. 30 * 31 * Note that testLoopRelations2() is suppressed because it fails in corner 32 * cases due to a problem with S2.robustCCW(). 33 * 34 */ 35 public strictfp class S2LoopTest extends GeometryTestCase { 36 private static final Logger log = Logger.getLogger(S2LoopTest.class.getCanonicalName()); 37 38 // A stripe that slightly over-wraps the equator. 39 private S2Loop candyCane = makeLoop("-20:150, -20:-70, 0:70, 10:-150, 10:70, -10:-70"); 40 41 // A small clockwise loop in the northern & eastern hemisperes. 42 private S2Loop smallNeCw = makeLoop("35:20, 45:20, 40:25"); 43 44 // Loop around the north pole at 80 degrees. 45 private S2Loop arctic80 = makeLoop("80:-150, 80:-30, 80:90"); 46 47 // Loop around the south pole at 80 degrees. 48 private S2Loop antarctic80 = makeLoop("-80:120, -80:0, -80:-120"); 49 50 // The northern hemisphere, defined using two pairs of antipodal points. 51 private S2Loop northHemi = makeLoop("0:-180, 0:-90, 0:0, 0:90"); 52 53 // The northern hemisphere, defined using three points 120 degrees apart. 54 private S2Loop northHemi3 = makeLoop("0:-180, 0:-60, 0:60"); 55 56 // The western hemisphere, defined using two pairs of antipodal points. 57 private S2Loop westHemi = makeLoop("0:-180, -90:0, 0:0, 90:0"); 58 59 // The "near" hemisphere, defined using two pairs of antipodal points. 60 private S2Loop nearHemi = makeLoop("0:-90, -90:0, 0:90, 90:0"); 61 62 // A diamond-shaped loop around the point 0:180. 63 private S2Loop loopA = makeLoop("0:178, -1:180, 0:-179, 1:-180"); 64 65 // Another diamond-shaped loop around the point 0:180. 66 private S2Loop loopB = makeLoop("0:179, -1:180, 0:-178, 1:-180"); 67 68 // The intersection of A and B. 69 private S2Loop aIntersectB = makeLoop("0:179, -1:180, 0:-179, 1:-180"); 70 71 // The union of A and B. 72 private S2Loop aUnionB = makeLoop("0:178, -1:180, 0:-178, 1:-180"); 73 74 // A minus B (concave) 75 private S2Loop aMinusB = makeLoop("0:178, -1:180, 0:179, 1:-180"); 76 77 // B minus A (concave) 78 private S2Loop bMinusA = makeLoop("0:-179, -1:180, 0:-178, 1:-180"); 79 80 // A self-crossing loop with a duplicated vertex 81 private S2Loop bowtie = makeLoop("0:0, 2:0, 1:1, 0:2, 2:2, 1:1"); 82 83 // Initialized below. 84 private S2Loop southHemi; 85 private S2Loop eastHemi; 86 private S2Loop farHemi; 87 88 @Override setUp()89 public void setUp() { 90 super.setUp(); 91 southHemi = new S2Loop(northHemi); 92 southHemi.invert(); 93 94 eastHemi = new S2Loop(westHemi); 95 eastHemi.invert(); 96 97 farHemi = new S2Loop(nearHemi); 98 farHemi.invert(); 99 } 100 testBounds()101 public void testBounds() { 102 assertTrue(candyCane.getRectBound().lng().isFull()); 103 assertTrue(candyCane.getRectBound().latLo().degrees() < -20); 104 assertTrue(candyCane.getRectBound().latHi().degrees() > 10); 105 assertTrue(smallNeCw.getRectBound().isFull()); 106 assertEquals(arctic80.getRectBound(), 107 new S2LatLngRect(S2LatLng.fromDegrees(80, -180), S2LatLng.fromDegrees(90, 180))); 108 assertEquals(antarctic80.getRectBound(), 109 new S2LatLngRect(S2LatLng.fromDegrees(-90, -180), S2LatLng.fromDegrees(-80, 180))); 110 111 arctic80.invert(); 112 // The highest latitude of each edge is attained at its midpoint. 113 S2Point mid = S2Point.mul(S2Point.add(arctic80.vertex(0), arctic80.vertex(1)), 0.5); 114 assertDoubleNear(arctic80.getRectBound().latHi().radians(), new S2LatLng(mid).lat().radians()); 115 arctic80.invert(); 116 117 assertTrue(southHemi.getRectBound().lng().isFull()); 118 assertEquals(southHemi.getRectBound().lat(), new R1Interval(-S2.M_PI_2, 0)); 119 } 120 testAreaCentroid()121 public void testAreaCentroid() { 122 assertDoubleNear(northHemi.getArea(), 2 * S2.M_PI); 123 assertDoubleNear(eastHemi.getArea(), 2 * S2.M_PI); 124 125 // Construct spherical caps of random height, and approximate their boundary 126 // with closely spaces vertices. Then check that the area and centroid are 127 // correct. 128 129 for (int i = 0; i < 100; ++i) { 130 // Choose a coordinate frame for the spherical cap. 131 S2Point x = randomPoint(); 132 S2Point y = S2Point.normalize(S2Point.crossProd(x, randomPoint())); 133 S2Point z = S2Point.normalize(S2Point.crossProd(x, y)); 134 135 // Given two points at latitude phi and whose longitudes differ by dtheta, 136 // the geodesic between the two points has a maximum latitude of 137 // atan(tan(phi) / cos(dtheta/2)). This can be derived by positioning 138 // the two points at (-dtheta/2, phi) and (dtheta/2, phi). 139 // 140 // We want to position the vertices close enough together so that their 141 // maximum distance from the boundary of the spherical cap is kMaxDist. 142 // Thus we want fabs(atan(tan(phi) / cos(dtheta/2)) - phi) <= kMaxDist. 143 double kMaxDist = 1e-6; 144 double height = 2 * rand.nextDouble(); 145 double phi = Math.asin(1 - height); 146 double maxDtheta = 147 2 * Math.acos(Math.tan(Math.abs(phi)) / Math.tan(Math.abs(phi) + kMaxDist)); 148 maxDtheta = Math.min(S2.M_PI, maxDtheta); // At least 3 vertices. 149 150 List<S2Point> vertices = Lists.newArrayList(); 151 for (double theta = 0; theta < 2 * S2.M_PI; theta += rand.nextDouble() * maxDtheta) { 152 153 S2Point xCosThetaCosPhi = S2Point.mul(x, (Math.cos(theta) * Math.cos(phi))); 154 S2Point ySinThetaCosPhi = S2Point.mul(y, (Math.sin(theta) * Math.cos(phi))); 155 S2Point zSinPhi = S2Point.mul(z, Math.sin(phi)); 156 157 S2Point sum = S2Point.add(S2Point.add(xCosThetaCosPhi, ySinThetaCosPhi), zSinPhi); 158 159 vertices.add(sum); 160 } 161 162 S2Loop loop = new S2Loop(vertices); 163 S2AreaCentroid areaCentroid = loop.getAreaAndCentroid(); 164 165 double area = loop.getArea(); 166 S2Point centroid = loop.getCentroid(); 167 double expectedArea = 2 * S2.M_PI * height; 168 assertTrue(areaCentroid.getArea() == area); 169 assertTrue(centroid.equals(areaCentroid.getCentroid())); 170 assertTrue(Math.abs(area - expectedArea) <= 2 * S2.M_PI * kMaxDist); 171 172 // high probability 173 assertTrue(Math.abs(area - expectedArea) >= 0.01 * kMaxDist); 174 175 S2Point expectedCentroid = S2Point.mul(z, expectedArea * (1 - 0.5 * height)); 176 177 assertTrue(S2Point.sub(centroid, expectedCentroid).norm() <= 2 * kMaxDist); 178 } 179 } 180 rotate(S2Loop loop)181 private S2Loop rotate(S2Loop loop) { 182 List<S2Point> vertices = Lists.newArrayList(); 183 for (int i = 1; i <= loop.numVertices(); ++i) { 184 vertices.add(loop.vertex(i)); 185 } 186 return new S2Loop(vertices); 187 } 188 testContains()189 public void testContains() { 190 assertTrue(candyCane.contains(S2LatLng.fromDegrees(5, 71).toPoint())); 191 for (int i = 0; i < 4; ++i) { 192 assertTrue(northHemi.contains(new S2Point(0, 0, 1))); 193 assertTrue(!northHemi.contains(new S2Point(0, 0, -1))); 194 assertTrue(!southHemi.contains(new S2Point(0, 0, 1))); 195 assertTrue(southHemi.contains(new S2Point(0, 0, -1))); 196 assertTrue(!westHemi.contains(new S2Point(0, 1, 0))); 197 assertTrue(westHemi.contains(new S2Point(0, -1, 0))); 198 assertTrue(eastHemi.contains(new S2Point(0, 1, 0))); 199 assertTrue(!eastHemi.contains(new S2Point(0, -1, 0))); 200 northHemi = rotate(northHemi); 201 southHemi = rotate(southHemi); 202 eastHemi = rotate(eastHemi); 203 westHemi = rotate(westHemi); 204 } 205 206 // This code checks each cell vertex is contained by exactly one of 207 // the adjacent cells. 208 for (int level = 0; level < 3; ++level) { 209 List<S2Loop> loops = Lists.newArrayList(); 210 List<S2Point> loopVertices = Lists.newArrayList(); 211 Set<S2Point> points = Sets.newHashSet(); 212 for (S2CellId id = S2CellId.begin(level); !id.equals(S2CellId.end(level)); id = id.next()) { 213 S2Cell cell = new S2Cell(id); 214 points.add(cell.getCenter()); 215 for (int k = 0; k < 4; ++k) { 216 loopVertices.add(cell.getVertex(k)); 217 points.add(cell.getVertex(k)); 218 } 219 loops.add(new S2Loop(loopVertices)); 220 loopVertices.clear(); 221 } 222 for (S2Point point : points) { 223 int count = 0; 224 for (int j = 0; j < loops.size(); ++j) { 225 if (loops.get(j).contains(point)) { 226 ++count; 227 } 228 } 229 assertEquals(count, 1); 230 } 231 } 232 } 233 advance(S2CellId id, int n)234 private S2CellId advance(S2CellId id, int n) { 235 while (id.isValid() && --n >= 0) { 236 id = id.next(); 237 } 238 return id; 239 } 240 makeCellLoop(S2CellId begin, S2CellId end)241 private S2Loop makeCellLoop(S2CellId begin, S2CellId end) { 242 // Construct a CCW polygon whose boundary is the union of the cell ids 243 // in the range [begin, end). We add the edges one by one, removing 244 // any edges that are already present in the opposite direction. 245 246 Map<S2Point, Set<S2Point>> edges = Maps.newHashMap(); 247 for (S2CellId id = begin; !id.equals(end); id = id.next()) { 248 S2Cell cell = new S2Cell(id); 249 for (int k = 0; k < 4; ++k) { 250 S2Point a = cell.getVertex(k); 251 S2Point b = cell.getVertex((k + 1) & 3); 252 if (edges.get(b) == null) { 253 edges.put(b, Sets.<S2Point>newHashSet()); 254 } 255 // if a is in b's set, remove it and remove b's set if it's empty 256 // otherwise, add b to a's set 257 if (!edges.get(b).remove(a)) { 258 if (edges.get(a) == null) { 259 edges.put(a, Sets.<S2Point>newHashSet()); 260 } 261 edges.get(a).add(b); 262 } else if (edges.get(b).isEmpty()) { 263 edges.remove(b); 264 } 265 } 266 } 267 268 // The remaining edges form a single loop. We simply follow it starting 269 // at an arbitrary vertex and build up a list of vertices. 270 271 List<S2Point> vertices = Lists.newArrayList(); 272 S2Point p = edges.keySet().iterator().next(); 273 while (!edges.isEmpty()) { 274 assertEquals(1, edges.get(p).size()); 275 S2Point next = edges.get(p).iterator().next(); 276 vertices.add(p); 277 edges.remove(p); 278 p = next; 279 } 280 return new S2Loop(vertices); 281 } 282 assertRelation( S2Loop a, S2Loop b, int containsOrCrosses, boolean intersects, boolean nestable)283 private void assertRelation( 284 S2Loop a, S2Loop b, int containsOrCrosses, boolean intersects, boolean nestable) { 285 assertEquals(a.contains(b), containsOrCrosses == 1); 286 assertEquals(a.intersects(b), intersects); 287 if (nestable) { 288 assertEquals(a.containsNested(b), a.contains(b)); 289 } 290 if (containsOrCrosses >= -1) { 291 assertEquals(a.containsOrCrosses(b), containsOrCrosses); 292 } 293 } 294 testLoopRelations()295 public void testLoopRelations() { 296 assertRelation(northHemi, northHemi, 1, true, false); 297 assertRelation(northHemi, southHemi, 0, false, false); 298 assertRelation(northHemi, eastHemi, -1, true, false); 299 assertRelation(northHemi, arctic80, 1, true, true); 300 assertRelation(northHemi, antarctic80, 0, false, true); 301 assertRelation(northHemi, candyCane, -1, true, false); 302 303 // We can't compare northHemi3 vs. northHemi or southHemi. 304 assertRelation(northHemi3, northHemi3, 1, true, false); 305 assertRelation(northHemi3, eastHemi, -1, true, false); 306 assertRelation(northHemi3, arctic80, 1, true, true); 307 assertRelation(northHemi3, antarctic80, 0, false, true); 308 assertRelation(northHemi3, candyCane, -1, true, false); 309 310 assertRelation(southHemi, northHemi, 0, false, false); 311 assertRelation(southHemi, southHemi, 1, true, false); 312 assertRelation(southHemi, farHemi, -1, true, false); 313 assertRelation(southHemi, arctic80, 0, false, true); 314 assertRelation(southHemi, antarctic80, 1, true, true); 315 assertRelation(southHemi, candyCane, -1, true, false); 316 317 assertRelation(candyCane, northHemi, -1, true, false); 318 assertRelation(candyCane, southHemi, -1, true, false); 319 assertRelation(candyCane, arctic80, 0, false, true); 320 assertRelation(candyCane, antarctic80, 0, false, true); 321 assertRelation(candyCane, candyCane, 1, true, false); 322 323 assertRelation(nearHemi, westHemi, -1, true, false); 324 325 assertRelation(smallNeCw, southHemi, 1, true, false); 326 assertRelation(smallNeCw, westHemi, 1, true, false); 327 assertRelation(smallNeCw, northHemi, -2, true, false); 328 assertRelation(smallNeCw, eastHemi, -2, true, false); 329 330 assertRelation(loopA, loopA, 1, true, false); 331 assertRelation(loopA, loopB, -1, true, false); 332 assertRelation(loopA, aIntersectB, 1, true, false); 333 assertRelation(loopA, aUnionB, 0, true, false); 334 assertRelation(loopA, aMinusB, 1, true, false); 335 assertRelation(loopA, bMinusA, 0, false, false); 336 337 assertRelation(loopB, loopA, -1, true, false); 338 assertRelation(loopB, loopB, 1, true, false); 339 assertRelation(loopB, aIntersectB, 1, true, false); 340 assertRelation(loopB, aUnionB, 0, true, false); 341 assertRelation(loopB, aMinusB, 0, false, false); 342 assertRelation(loopB, bMinusA, 1, true, false); 343 344 assertRelation(aIntersectB, loopA, 0, true, false); 345 assertRelation(aIntersectB, loopB, 0, true, false); 346 assertRelation(aIntersectB, aIntersectB, 1, true, false); 347 assertRelation(aIntersectB, aUnionB, 0, true, true); 348 assertRelation(aIntersectB, aMinusB, 0, false, false); 349 assertRelation(aIntersectB, bMinusA, 0, false, false); 350 351 assertRelation(aUnionB, loopA, 1, true, false); 352 assertRelation(aUnionB, loopB, 1, true, false); 353 assertRelation(aUnionB, aIntersectB, 1, true, true); 354 assertRelation(aUnionB, aUnionB, 1, true, false); 355 assertRelation(aUnionB, aMinusB, 1, true, false); 356 assertRelation(aUnionB, bMinusA, 1, true, false); 357 358 assertRelation(aMinusB, loopA, 0, true, false); 359 assertRelation(aMinusB, loopB, 0, false, false); 360 assertRelation(aMinusB, aIntersectB, 0, false, false); 361 assertRelation(aMinusB, aUnionB, 0, true, false); 362 assertRelation(aMinusB, aMinusB, 1, true, false); 363 assertRelation(aMinusB, bMinusA, 0, false, true); 364 365 assertRelation(bMinusA, loopA, 0, false, false); 366 assertRelation(bMinusA, loopB, 0, true, false); 367 assertRelation(bMinusA, aIntersectB, 0, false, false); 368 assertRelation(bMinusA, aUnionB, 0, true, false); 369 assertRelation(bMinusA, aMinusB, 0, false, true); 370 assertRelation(bMinusA, bMinusA, 1, true, false); 371 } 372 373 /** 374 * TODO(user, ericv) Fix this test. It fails sporadically. 375 * <p> 376 * The problem is not in this test, it is that 377 * {@link S2#robustCCW(S2Point, S2Point, S2Point)} currently requires 378 * arbitrary-precision arithmetic to be truly robust. That means it can give 379 * the wrong answers in cases where we are trying to determine edge 380 * intersections. 381 * <p> 382 * It seems the strictfp modifier here in java (required for correctness in 383 * other areas of the library) restricts the size of temporary registers, 384 * causing us to lose some of the precision that the C++ version gets. 385 * <p> 386 * This test fails when it randomly chooses a cell loop with nearly colinear 387 * edges. That's where S2.robustCCW provides the wrong answer. Note that there 388 * is an attempted workaround in {@link S2Loop#isValid()}, but it 389 * does not cover all cases. 390 */ suppressedTestLoopRelations2()391 public void suppressedTestLoopRelations2() { 392 // Construct polygons consisting of a sequence of adjacent cell ids 393 // at some fixed level. Comparing two polygons at the same level 394 // ensures that there are no T-vertices. 395 for (int iter = 0; iter < 1000; ++iter) { 396 long num = rand.nextLong(); 397 S2CellId begin = new S2CellId(num | 1); 398 if (!begin.isValid()) { 399 continue; 400 } 401 begin = begin.parent((int) Math.round(rand.nextDouble() * S2CellId.MAX_LEVEL)); 402 S2CellId aBegin = advance(begin, skewed(6)); 403 S2CellId aEnd = advance(aBegin, skewed(6) + 1); 404 S2CellId bBegin = advance(begin, skewed(6)); 405 S2CellId bEnd = advance(bBegin, skewed(6) + 1); 406 if (!aEnd.isValid() || !bEnd.isValid()) { 407 continue; 408 } 409 410 S2Loop a = makeCellLoop(aBegin, aEnd); 411 S2Loop b = makeCellLoop(bBegin, bEnd); 412 boolean contained = (aBegin.lessOrEquals(bBegin) && bEnd.lessOrEquals(aEnd)); 413 boolean intersects = (aBegin.lessThan(bEnd) && bBegin.lessThan(aEnd)); 414 log.info( 415 "Checking " + a.numVertices() + " vs. " + b.numVertices() + ", contained = " + contained 416 + ", intersects = " + intersects); 417 418 assertEquals(contained, a.contains(b)); 419 assertEquals(intersects, a.intersects(b)); 420 } 421 } 422 423 /** 424 * Tests that nearly colinear points pass S2Loop.isValid() 425 */ testRoundingError()426 public void testRoundingError() { 427 S2Point a = new S2Point(-0.9190364081111774, 0.17231932652084575, 0.35451111445694833); 428 S2Point b = new S2Point(-0.92130667053206, 0.17274500072476123, 0.3483578383756171); 429 S2Point c = new S2Point(-0.9257244057938284, 0.17357332608634282, 0.3360158106235289); 430 S2Point d = new S2Point(-0.9278712595449962, 0.17397586116468677, 0.32982923679138537); 431 432 assertTrue(S2Loop.isValid(Lists.newArrayList(a, b, c, d))); 433 } 434 435 /** 436 * Tests {@link S2Loop#isValid()}. 437 */ testIsValid()438 public void testIsValid() { 439 assertTrue(loopA.isValid()); 440 assertTrue(loopB.isValid()); 441 assertFalse(bowtie.isValid()); 442 } 443 444 /** 445 * Tests {@link S2Loop#compareTo(S2Loop)}. 446 */ testComparisons()447 public void testComparisons() { 448 S2Loop abc = makeLoop("0:1, 0:2, 1:2"); 449 S2Loop abcd = makeLoop("0:1, 0:2, 1:2, 1:1"); 450 S2Loop abcde = makeLoop("0:1, 0:2, 1:2, 1:1, 1:0"); 451 assertTrue(abc.compareTo(abcd) < 0); 452 assertTrue(abc.compareTo(abcde) < 0); 453 assertTrue(abcd.compareTo(abcde) < 0); 454 assertTrue(abcd.compareTo(abc) > 0); 455 assertTrue(abcde.compareTo(abc) > 0); 456 assertTrue(abcde.compareTo(abcd) > 0); 457 458 S2Loop bcda = makeLoop("0:2, 1:2, 1:1, 0:1"); 459 assertEquals(0, abcd.compareTo(bcda)); 460 assertEquals(0, bcda.compareTo(abcd)); 461 462 S2Loop wxyz = makeLoop("10:11, 10:12, 11:12, 11:11"); 463 assertTrue(abcd.compareTo(wxyz) > 0); 464 assertTrue(wxyz.compareTo(abcd) < 0); 465 } 466 467 public void testGetDistance() { 468 // Error margin since we're doing numerical computations 469 double epsilon = 1e-15; 470 471 // A square with (lat,lng) vertices (0,1), (1,1), (1,2) and (0,2) 472 // Tests the case where the shortest distance is along a normal to an edge, 473 // onto a vertex 474 S2Loop s1 = makeLoop("0:1, 1:1, 1:2, 0:2"); 475 476 // A square with (lat,lng) vertices (-1,1), (1,1), (1,2) and (-1,2) 477 // Tests the case where the shortest distance is along a normal to an edge, 478 // not onto a vertex 479 S2Loop s2 = makeLoop("-1:1, 1:1, 1:2, -1:2"); 480 481 // A diamond with (lat,lng) vertices (1,0), (2,1), (3,0) and (2,-1) 482 // Test the case where the shortest distance is NOT along a normal to an 483 // edge 484 S2Loop s3 = makeLoop("1:0, 2:1, 3:0, 2:-1"); 485 486 // All the vertices should be distance 0 487 for (int i = 0; i < s1.numVertices(); i++) { 488 assertEquals(0d, s1.getDistance(s1.vertex(i)).radians(), epsilon); 489 } 490 491 // A point on one of the edges should be distance 0 492 assertEquals(0d, s1.getDistance(S2LatLng.fromDegrees(0.5, 1).toPoint()).radians(), epsilon); 493 494 // In all three cases, the closest point to the origin is (0,1), which is at 495 // a distance of 1 degree. 496 // Note: all of these are intentionally distances measured along the 497 // equator, since that makes the math significantly simpler. Otherwise, the 498 // distance wouldn't actually be 1 degree. 499 S2Point origin = S2LatLng.fromDegrees(0, 0).toPoint(); 500 assertEquals(1d, s1.getDistance(origin).degrees(), epsilon); 501 assertEquals(1d, s2.getDistance(origin).degrees(), epsilon); 502 assertEquals(1d, s3.getDistance(origin).degrees(), epsilon); 503 } 504 505 /** 506 * This function is useful for debugging. 507 */ 508 @SuppressWarnings("unused") 509 private void dumpCrossings(S2Loop loop) { 510 511 System.out.println("Ortho(v1): " + S2.ortho(loop.vertex(1))); 512 System.out.printf("Contains(kOrigin): %b\n", loop.contains(S2.origin())); 513 for (int i = 1; i <= loop.numVertices(); ++i) { 514 S2Point a = S2.ortho(loop.vertex(i)); 515 S2Point b = loop.vertex(i - 1); 516 S2Point c = loop.vertex(i + 1); 517 S2Point o = loop.vertex(i); 518 System.out.printf("Vertex %d: [%.17g, %.17g, %.17g], " 519 + "%d%dR=%d, %d%d%d=%d, R%d%d=%d, inside: %b\n", 520 i, 521 loop.vertex(i).x, 522 loop.vertex(i).y, 523 loop.vertex(i).z, 524 i - 1, 525 i, 526 S2.robustCCW(b, o, a), 527 i + 1, 528 i, 529 i - 1, 530 S2.robustCCW(c, o, b), 531 i, 532 i + 1, 533 S2.robustCCW(a, o, c), 534 S2.orderedCCW(a, b, c, o)); 535 } 536 for (int i = 0; i < loop.numVertices() + 2; ++i) { 537 S2Point orig = S2.origin(); 538 S2Point dest; 539 if (i < loop.numVertices()) { 540 dest = loop.vertex(i); 541 System.out.printf("Origin->%d crosses:", i); 542 } else { 543 dest = new S2Point(0, 0, 1); 544 if (i == loop.numVertices() + 1) { 545 orig = loop.vertex(1); 546 } 547 System.out.printf("Case %d:", i); 548 } 549 for (int j = 0; j < loop.numVertices(); ++j) { 550 System.out.println( 551 " " + S2EdgeUtil.edgeOrVertexCrossing(orig, dest, loop.vertex(j), loop.vertex(j + 1))); 552 } 553 System.out.println(); 554 } 555 for (int i = 0; i <= 2; i += 2) { 556 System.out.printf("Origin->v1 crossing v%d->v1: ", i); 557 S2Point a = S2.ortho(loop.vertex(1)); 558 S2Point b = loop.vertex(i); 559 S2Point c = S2.origin(); 560 S2Point o = loop.vertex(1); 561 System.out.printf("%d1R=%d, M1%d=%d, R1M=%d, crosses: %b\n", 562 i, 563 S2.robustCCW(b, o, a), 564 i, 565 S2.robustCCW(c, o, b), 566 S2.robustCCW(a, o, c), 567 S2EdgeUtil.edgeOrVertexCrossing(c, o, b, a)); 568 } 569 } 570 } 571