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 21 import java.util.List; 22 23 /** 24 * Tests for {@link S2Polygon}. 25 * 26 */ 27 public strictfp class S2PolygonTest extends GeometryTestCase { 28 29 // A set of nested loops around the point 0:0 (lat:lng). 30 // Every vertex of NEAR0 is a vertex of NEAR1. 31 private static final String NEAR0 = "-1:0, 0:1, 1:0, 0:-1;"; 32 private static final String NEAR1 = "-1:-1, -1:0, -1:1, 0:1, 1:1, 1:0, 1:-1, 0:-1;"; 33 private static final String NEAR2 = "5:-2, -2:5, -1:-2;"; 34 private static final String NEAR3 = "6:-3, -3:6, -2:-2;"; 35 private static final String NEAR_HEMI = "0:-90, -90:0, 0:90, 90:0;"; 36 37 // A set of nested loops around the point 0:180 (lat:lng). 38 // Every vertex of FAR0 and FAR2 belongs to FAR1, and all 39 // the loops except FAR2 are non-convex. 40 private static final String FAR0 = "0:179, 1:180, 0:-179, 2:-180;"; 41 private static final String FAR1 = 42 "0:179, -1:179, 1:180, -1:-179, 0:-179, 3:-178, 2:-180, 3:178;"; 43 private static final String FAR2 = "-1:-179, -1:179, 3:178, 3:-178;"; // opposite 44 // direction 45 private static final String FAR3 = "-3:-178, -2:179, -3:178, 4:177, 4:-177;"; 46 private static final String FAR_HEMI = "0:-90, 60:90, -60:90;"; 47 48 // A set of nested loops around the point -90:0 (lat:lng). 49 private static final String SOUTH0a = "-90:0, -89.99:0, -89.99:0.01;"; 50 private static final String SOUTH0b = "-90:0, -89.99:0.02, -89.99:0.03;"; 51 private static final String SOUTH0c = "-90:0, -89.99:0.04, -89.99:0.05;"; 52 private static final String SOUTH1 = "-90:0, -89.9:-0.1, -89.9:0.1;"; 53 private static final String SOUTH2 = "-90:0, -89.8:-0.2, -89.8:0.2;"; 54 private static final String SOUTH_HEMI = "0:-180, 0:60, 0:-60;"; 55 56 // Two different loops that surround all the Near and Far loops except 57 // for the hemispheres. 58 private static final String NEAR_FAR1 = 59 "-1:-9, -9:-9, -9:9, 9:9, 9:-9, 1:-9, " + "1:-175, 9:-175, 9:175, -9:175, -9:-175, -1:-175;"; 60 private static final String NEAR_FAR2 = 61 "-8:-4, 8:-4, 2:15, 2:170, 8:-175, -8:-175, -2:170, -2:15;"; 62 63 // Two rectangles that are "adjacent", but rather than having common edges, 64 // those edges are slighly off. A third rectangle that is not adjacent to 65 // either of the first two. 66 private static final String ADJACENT0 = "0:1, 1:1, 2:1, 2:0, 1:0, 0:0;"; 67 private static final String ADJACENT1 = "0:2, 1:2, 2:2, 2:1.01, 1:0.99, 0:1.01;"; 68 private static final String UN_ADJACENT = "10:10, 11:10, 12:10, 12:9, 11:9, 10:9;"; 69 70 // Shapes used to test comparison functions for polygons. 71 private static final String RECTANGLE1 = "0:1, 1:1, 2:1, 2:0, 1:0, 0:0;"; 72 private static final String RECTANGLE2 = "5:1, 6:1, 7:1, 7:0, 6:0, 5:0;"; 73 private static final String TRIANGLE = "15:0, 17:0, 16:2;"; 74 private static final String TRIANGLE_ROT = "17:0, 16:2, 15:0;"; 75 assertContains(String aStr, String bStr)76 private void assertContains(String aStr, String bStr) { 77 S2Polygon a = makePolygon(aStr); 78 S2Polygon b = makePolygon(bStr); 79 assertTrue(a.contains(b)); 80 } 81 82 // Make sure we've set things up correctly. testInit()83 public void testInit() { 84 assertContains(NEAR1, NEAR0); 85 assertContains(NEAR2, NEAR1); 86 assertContains(NEAR3, NEAR2); 87 assertContains(NEAR_HEMI, NEAR3); 88 assertContains(FAR1, FAR0); 89 assertContains(FAR2, FAR1); 90 assertContains(FAR3, FAR2); 91 assertContains(FAR_HEMI, FAR3); 92 assertContains(SOUTH1, SOUTH0a); 93 assertContains(SOUTH1, SOUTH0b); 94 assertContains(SOUTH1, SOUTH0c); 95 assertContains(SOUTH_HEMI, SOUTH2); 96 assertContains(NEAR_FAR1, NEAR3); 97 assertContains(NEAR_FAR1, FAR3); 98 assertContains(NEAR_FAR2, NEAR3); 99 assertContains(NEAR_FAR2, FAR3); 100 } 101 102 S2Polygon near10 = makePolygon(NEAR0 + NEAR1); 103 S2Polygon near30 = makePolygon(NEAR3 + NEAR0); 104 S2Polygon near32 = makePolygon(NEAR2 + NEAR3); 105 S2Polygon near3210 = makePolygon(NEAR0 + NEAR2 + NEAR3 + NEAR1); 106 S2Polygon nearH3210 = makePolygon(NEAR0 + NEAR2 + NEAR3 + NEAR_HEMI + NEAR1); 107 108 S2Polygon far10 = makePolygon(FAR0 + FAR1); 109 S2Polygon far21 = makePolygon(FAR2 + FAR1); 110 S2Polygon far321 = makePolygon(FAR2 + FAR3 + FAR1); 111 S2Polygon farH20 = makePolygon(FAR2 + FAR_HEMI + FAR0); 112 S2Polygon farH3210 = makePolygon(FAR2 + FAR_HEMI + FAR0 + FAR1 + FAR3); 113 114 S2Polygon south0ab = makePolygon(SOUTH0a + SOUTH0b); 115 S2Polygon south2 = makePolygon(SOUTH2); 116 S2Polygon south210b = makePolygon(SOUTH2 + SOUTH0b + SOUTH1); 117 S2Polygon southH21 = makePolygon(SOUTH2 + SOUTH_HEMI + SOUTH1); 118 S2Polygon southH20abc = makePolygon(SOUTH2 + SOUTH0b + SOUTH_HEMI + SOUTH0a + SOUTH0c); 119 120 S2Polygon nf1n10f2s10abc = 121 makePolygon(SOUTH0c + FAR2 + NEAR1 + NEAR_FAR1 + NEAR0 + SOUTH1 + SOUTH0b + SOUTH0a); 122 123 S2Polygon nf2n2f210s210ab = 124 makePolygon(FAR2 + SOUTH0a + FAR1 + SOUTH1 + FAR0 + SOUTH0b + NEAR_FAR2 + SOUTH2 + NEAR2); 125 126 S2Polygon f32n0 = makePolygon(FAR2 + NEAR0 + FAR3); 127 S2Polygon n32s0b = makePolygon(NEAR3 + SOUTH0b + NEAR2); 128 129 S2Polygon adj0 = makePolygon(ADJACENT0); 130 S2Polygon adj1 = makePolygon(ADJACENT1); 131 S2Polygon unAdj = makePolygon(UN_ADJACENT); 132 assertRelation(S2Polygon a, S2Polygon b, int contains, boolean intersects)133 private void assertRelation(S2Polygon a, S2Polygon b, int contains, boolean intersects) { 134 assertEquals(a.contains(b), contains > 0); 135 assertEquals(b.contains(a), contains < 0); 136 assertEquals(a.intersects(b), intersects); 137 } 138 139 public void testRelations() { 140 assertRelation(near10, near30, -1, true); 141 assertRelation(near10, near32, 0, false); 142 assertRelation(near10, near3210, -1, true); 143 assertRelation(near10, nearH3210, 0, false); 144 assertRelation(near30, near32, 1, true); 145 assertRelation(near30, near3210, 1, true); 146 assertRelation(near30, nearH3210, 0, true); 147 assertRelation(near32, near3210, -1, true); 148 assertRelation(near32, nearH3210, 0, false); 149 assertRelation(near3210, nearH3210, 0, false); 150 151 assertRelation(far10, far21, 0, false); 152 assertRelation(far10, far321, -1, true); 153 assertRelation(far10, farH20, 0, false); 154 assertRelation(far10, farH3210, 0, false); 155 assertRelation(far21, far321, 0, false); 156 assertRelation(far21, farH20, 0, false); 157 assertRelation(far21, farH3210, -1, true); 158 assertRelation(far321, farH20, 0, true); 159 assertRelation(far321, farH3210, 0, true); 160 assertRelation(farH20, farH3210, 0, true); 161 162 assertRelation(south0ab, south2, -1, true); 163 assertRelation(south0ab, south210b, 0, true); 164 assertRelation(south0ab, southH21, -1, true); 165 assertRelation(south0ab, southH20abc, -1, true); 166 assertRelation(south2, south210b, 1, true); 167 assertRelation(south2, southH21, 0, true); 168 assertRelation(south2, southH20abc, 0, true); 169 assertRelation(south210b, southH21, 0, true); 170 assertRelation(south210b, southH20abc, 0, true); 171 assertRelation(southH21, southH20abc, 1, true); 172 173 assertRelation(nf1n10f2s10abc, nf2n2f210s210ab, 0, true); 174 assertRelation(nf1n10f2s10abc, near32, 1, true); 175 assertRelation(nf1n10f2s10abc, far21, 0, false); 176 assertRelation(nf1n10f2s10abc, south0ab, 0, false); 177 assertRelation(nf1n10f2s10abc, f32n0, 1, true); 178 179 assertRelation(nf2n2f210s210ab, near10, 0, false); 180 assertRelation(nf2n2f210s210ab, far10, 1, true); 181 assertRelation(nf2n2f210s210ab, south210b, 1, true); 182 assertRelation(nf2n2f210s210ab, south0ab, 1, true); 183 assertRelation(nf2n2f210s210ab, n32s0b, 1, true); 184 } 185 186 private void assertPointApproximatelyEquals( 187 S2Loop s2Loop, int vertexIndex, double lat, double lng, double error) { 188 S2LatLng latLng = new S2LatLng(s2Loop.vertex(vertexIndex)); 189 assertDoubleNear(latLng.latDegrees(), lat, error); 190 assertDoubleNear(latLng.lngDegrees(), lng, error); 191 } 192 193 private void checkEqual(S2Polygon a, S2Polygon b) { 194 final double MAX_ERROR = 1e-31; 195 196 if (a.isNormalized() && b.isNormalized()) { 197 boolean r = a.boundaryApproxEquals(b, MAX_ERROR); 198 assertTrue(r); 199 } else { 200 S2PolygonBuilder builder = new S2PolygonBuilder(S2PolygonBuilder.Options.UNDIRECTED_XOR); 201 S2Polygon a2 = new S2Polygon(); 202 S2Polygon b2 = new S2Polygon(); 203 builder.addPolygon(a); 204 assertTrue(builder.assemblePolygon(a2, null)); 205 builder.addPolygon(b); 206 assertTrue(builder.assemblePolygon(b2, null)); 207 assertTrue(a2.boundaryApproxEquals(b2, MAX_ERROR)); 208 } 209 } 210 211 public void tryUnion(S2Polygon a, S2Polygon b) { 212 S2Polygon union = new S2Polygon(); 213 union.initToUnion(a, b); 214 215 List<S2Polygon> polygons = Lists.newArrayList(); 216 polygons.add(new S2Polygon(a)); 217 polygons.add(new S2Polygon(b)); 218 S2Polygon destructiveUnion = S2Polygon.destructiveUnion(polygons); 219 220 checkEqual(union, destructiveUnion); 221 } 222 223 public void testDisjoint() { 224 S2PolygonBuilder builder = new S2PolygonBuilder(S2PolygonBuilder.Options.UNDIRECTED_XOR); 225 builder.addPolygon(adj0); 226 builder.addPolygon(unAdj); 227 S2Polygon ab = new S2Polygon(); 228 assertTrue(builder.assemblePolygon(ab, null)); 229 230 S2Polygon union = new S2Polygon(); 231 union.initToUnion(adj0, unAdj); 232 assertEquals(2, union.numLoops()); 233 234 checkEqual(ab, union); 235 tryUnion(adj0, unAdj); 236 } 237 238 // Android-changed: Commented test. Does not pass on host or device. 239 /* 240 public void testUnionSloppySuccess() { 241 List<S2Polygon> polygons = Lists.newArrayList(); 242 polygons.add(adj0); 243 polygons.add(adj1); 244 S2Polygon union = S2Polygon.destructiveUnionSloppy(polygons, S1Angle.degrees(0.1)); 245 246 assertEquals(1, union.numLoops()); 247 if (union.numLoops() != 1) { 248 return; 249 } 250 S2Loop s2Loop = union.loop(0); 251 assertEquals(8, s2Loop.numVertices()); 252 if (s2Loop.numVertices() != 8) { 253 return; 254 } 255 assertPointApproximatelyEquals(s2Loop, 0, 2.0, 0.0, 0.01); 256 assertPointApproximatelyEquals(s2Loop, 1, 1.0, 0.0, 0.01); 257 assertPointApproximatelyEquals(s2Loop, 2, 0.0, 0.0, 0.01); 258 assertPointApproximatelyEquals(s2Loop, 3, 0.0, 1.0, 0.01); 259 assertPointApproximatelyEquals(s2Loop, 4, 0.0, 2.0, 0.01); 260 assertPointApproximatelyEquals(s2Loop, 5, 1.0, 2.0, 0.01); 261 assertPointApproximatelyEquals(s2Loop, 6, 2.0, 2.0, 0.01); 262 assertPointApproximatelyEquals(s2Loop, 7, 2.0, 1.0, 0.01); 263 } 264 */ 265 266 public void testUnionSloppyFailure() { 267 List<S2Polygon> polygons = Lists.newArrayList(); 268 polygons.add(adj0); 269 polygons.add(unAdj); 270 // The polygons are sufficiently far apart that this angle will not 271 // bring them together: 272 S2Polygon union = S2Polygon.destructiveUnionSloppy(polygons, S1Angle.degrees(0.1)); 273 274 assertEquals(2, union.numLoops()); 275 } 276 277 public void testCompareTo() { 278 // Polygons with same loops, but in different order: 279 S2Polygon p1 = makePolygon(RECTANGLE1 + RECTANGLE2); 280 S2Polygon p2 = makePolygon(RECTANGLE2 + RECTANGLE1); 281 assertEquals(0, p1.compareTo(p2)); 282 283 // Polygons with same loops, but in different order and containins a 284 // different number of points. 285 S2Polygon p3 = makePolygon(RECTANGLE1 + TRIANGLE); 286 S2Polygon p4 = makePolygon(TRIANGLE + RECTANGLE1); 287 assertEquals(0, p3.compareTo(p4)); 288 289 // Polygons with same logical loop (but loop is reordered). 290 S2Polygon p5 = makePolygon(TRIANGLE); 291 S2Polygon p6 = makePolygon(TRIANGLE_ROT); 292 assertEquals(0, p5.compareTo(p6)); 293 294 // Polygons with a differing number of loops 295 S2Polygon p7 = makePolygon(RECTANGLE1 + RECTANGLE2); 296 S2Polygon p8 = makePolygon(TRIANGLE); 297 assertTrue(0 > p8.compareTo(p7)); 298 assertTrue(0 < p7.compareTo(p8)); 299 300 // Polygons with a differing number of loops (one a subset of the other) 301 S2Polygon p9 = makePolygon(RECTANGLE1 + RECTANGLE2 + TRIANGLE); 302 S2Polygon p10 = makePolygon(RECTANGLE1 + RECTANGLE2); 303 assertTrue(0 < p9.compareTo(p10)); 304 assertTrue(0 > p10.compareTo(p9)); 305 } 306 testGetDistance()307 public void testGetDistance() { 308 // Error margin since we're doing numerical computations 309 double epsilon = 1e-15; 310 311 // A rectangle with (lat,lng) vertices (3,1), (3,-1), (-3,-1) and (-3,1) 312 String inner = "3:1, 3:-1, -3:-1, -3:1;"; 313 // A larger rectangle with (lat,lng) vertices (4,2), (4,-2), (-4,-2) and 314 // (-4,s) 315 String outer = "4:2, 4:-2, -4:-2, -4:2;"; 316 317 318 S2Polygon rect = makePolygon(inner); 319 S2Polygon shell = makePolygon(inner + outer); 320 321 // All of the vertices of a polygon should be distance 0 322 for (int i = 0; i < shell.numLoops(); i++) { 323 for (int j = 0; j < shell.loop(i).numVertices(); j++) { 324 assertEquals(0d, shell.getDistance(shell.loop(i).vertex(j)).radians(), epsilon); 325 } 326 } 327 328 // A non-vertex point on an edge should be distance 0 329 assertEquals(0d, rect.getDistance( 330 S2Point.normalize(S2Point.add(rect.loop(0).vertex(0), rect.loop(0).vertex(1)))).radians(), 331 epsilon); 332 333 S2Point origin = S2LatLng.fromDegrees(0, 0).toPoint(); 334 // rect contains the origin 335 assertEquals(0d, rect.getDistance(origin).radians(), epsilon); 336 337 // shell does NOT contain the origin, since it has a hole. The shortest 338 // distance is to (1,0) or (-1,0), and should be 1 degree 339 assertEquals(1d, shell.getDistance(origin).degrees(), epsilon); 340 } 341 } 342