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 junit.framework.Assert; 22 23 import java.util.List; 24 25 /** 26 * Tests for {@link S2Polyline}. 27 * 28 */ 29 public strictfp class S2PolylineTest extends GeometryTestCase { 30 31 @Override setUp()32 public void setUp() { 33 super.setUp(); 34 } 35 testBasic()36 public void testBasic() { 37 List<S2Point> vertices = Lists.newArrayList(); 38 S2Polyline empty = new S2Polyline(vertices); 39 assertEquals(empty.getRectBound(), S2LatLngRect.empty()); 40 } 41 testGetLengthCentroid()42 public void testGetLengthCentroid() { 43 // Construct random great circles and divide them randomly into segments. 44 // Then make sure that the length and centroid are correct. Note that 45 // because of the way the centroid is computed, it does not matter how 46 // we split the great circle into segments. 47 48 for (int i = 0; i < 100; ++i) { 49 // Choose a coordinate frame for the great circle. 50 S2Point x = randomPoint(); 51 S2Point y = S2Point.normalize(S2Point.crossProd(x, randomPoint())); 52 S2Point z = S2Point.normalize(S2Point.crossProd(x, y)); 53 54 List<S2Point> vertices = Lists.newArrayList(); 55 for (double theta = 0; theta < 2 * S2.M_PI; theta += Math.pow(rand.nextDouble(), 10)) { 56 S2Point p = S2Point.add(S2Point.mul(x, Math.cos(theta)), S2Point.mul(y, Math.sin(theta))); 57 if (vertices.isEmpty() || !p.equals(vertices.get(vertices.size() - 1))) { 58 vertices.add(p); 59 } 60 } 61 // Close the circle. 62 vertices.add(vertices.get(0)); 63 S2Polyline line = new S2Polyline(vertices); 64 S1Angle length = line.getArclengthAngle(); 65 assertTrue(Math.abs(length.radians() - 2 * S2.M_PI) < 2e-14); 66 } 67 } 68 69 public void testMayIntersect() { 70 List<S2Point> vertices = Lists.newArrayList(); 71 vertices.add(S2Point.normalize(new S2Point(1, -1.1, 0.8))); 72 vertices.add(S2Point.normalize(new S2Point(1, -0.8, 1.1))); 73 S2Polyline line = new S2Polyline(vertices); 74 for (int face = 0; face < 6; ++face) { 75 S2Cell cell = S2Cell.fromFacePosLevel(face, (byte) 0, 0); 76 assertEquals(line.mayIntersect(cell), (face & 1) == 0); 77 } 78 } 79 80 public void testInterpolate() { 81 List<S2Point> vertices = Lists.newArrayList(); 82 vertices.add(new S2Point(1, 0, 0)); 83 vertices.add(new S2Point(0, 1, 0)); 84 vertices.add(S2Point.normalize(new S2Point(0, 1, 1))); 85 vertices.add(new S2Point(0, 0, 1)); 86 S2Polyline line = new S2Polyline(vertices); 87 88 assertEquals(line.interpolate(-0.1), vertices.get(0)); 89 assertTrue(S2.approxEquals( 90 line.interpolate(0.1), S2Point.normalize(new S2Point(1, Math.tan(0.2 * S2.M_PI / 2), 0)))); 91 assertTrue(S2.approxEquals(line.interpolate(0.25), S2Point.normalize(new S2Point(1, 1, 0)))); 92 93 assertEquals(line.interpolate(0.5), vertices.get(1)); 94 assertEquals(line.interpolate(0.75), vertices.get(2)); 95 assertEquals(line.interpolate(1.1), vertices.get(3)); 96 } 97 98 public void testEqualsAndHashCode() { 99 List<S2Point> vertices = Lists.newArrayList(); 100 vertices.add(new S2Point(1, 0, 0)); 101 vertices.add(new S2Point(0, 1, 0)); 102 vertices.add(S2Point.normalize(new S2Point(0, 1, 1))); 103 vertices.add(new S2Point(0, 0, 1)); 104 105 106 S2Polyline line1 = new S2Polyline(vertices); 107 S2Polyline line2 = new S2Polyline(vertices); 108 109 checkEqualsAndHashCodeMethods(line1, line2, true); 110 111 List<S2Point> moreVertices = Lists.newLinkedList(vertices); 112 moreVertices.remove(0); 113 114 S2Polyline line3 = new S2Polyline(moreVertices); 115 116 checkEqualsAndHashCodeMethods(line1, line3, false); 117 checkEqualsAndHashCodeMethods(line1, null, false); 118 checkEqualsAndHashCodeMethods(line1, "", false); 119 } 120 121 public void testProject() { 122 List<S2Point> latLngs = Lists.newArrayList(); 123 latLngs.add(S2LatLng.fromDegrees(0, 0).toPoint()); 124 latLngs.add(S2LatLng.fromDegrees(0, 1).toPoint()); 125 latLngs.add(S2LatLng.fromDegrees(0, 2).toPoint()); 126 latLngs.add(S2LatLng.fromDegrees(1, 2).toPoint()); 127 S2Polyline line = new S2Polyline(latLngs); 128 129 int edgeIndex = -1; 130 S2Point testPoint = null; 131 132 testPoint = S2LatLng.fromDegrees(0.5, -0.5).toPoint(); 133 edgeIndex = line.getNearestEdgeIndex(testPoint); 134 assertTrue(S2.approxEquals( 135 line.projectToEdge(testPoint, edgeIndex), S2LatLng.fromDegrees(0, 0).toPoint())); 136 assertEquals(0, edgeIndex); 137 138 testPoint = S2LatLng.fromDegrees(0.5, 0.5).toPoint(); 139 edgeIndex = line.getNearestEdgeIndex(testPoint); 140 assertTrue(S2.approxEquals( 141 line.projectToEdge(testPoint, edgeIndex), S2LatLng.fromDegrees(0, 0.5).toPoint())); 142 assertEquals(0, edgeIndex); 143 144 testPoint = S2LatLng.fromDegrees(0.5, 1).toPoint(); 145 edgeIndex = line.getNearestEdgeIndex(testPoint); 146 assertTrue(S2.approxEquals( 147 line.projectToEdge(testPoint, edgeIndex), S2LatLng.fromDegrees(0, 1).toPoint())); 148 assertEquals(0, edgeIndex); 149 150 testPoint = S2LatLng.fromDegrees(-0.5, 2.5).toPoint(); 151 edgeIndex = line.getNearestEdgeIndex(testPoint); 152 assertTrue(S2.approxEquals( 153 line.projectToEdge(testPoint, edgeIndex), S2LatLng.fromDegrees(0, 2).toPoint())); 154 assertEquals(1, edgeIndex); 155 156 testPoint = S2LatLng.fromDegrees(2, 2).toPoint(); 157 edgeIndex = line.getNearestEdgeIndex(testPoint); 158 assertTrue(S2.approxEquals( 159 line.projectToEdge(testPoint, edgeIndex), S2LatLng.fromDegrees(1, 2).toPoint())); 160 assertEquals(2, edgeIndex); 161 } 162 163 /** 164 * Utility for testing equals() and hashCode() results at once. 165 * Tests that lhs.equals(rhs) matches expectedResult, as well as 166 * rhs.equals(lhs). Also tests that hashCode() return values are 167 * equal if expectedResult is true. (hashCode() is not tested if 168 * expectedResult is false, as unequal objects can have equal hashCodes.) 169 * 170 * @param lhs An Object for which equals() and hashCode() are to be tested. 171 * @param rhs As lhs. 172 * @param expectedResult True if the objects should compare equal, 173 * false if not. 174 */ 175 private static void checkEqualsAndHashCodeMethods(Object lhs, Object rhs, 176 boolean expectedResult) { 177 if ((lhs == null) && (rhs == null)) { 178 Assert.assertTrue( 179 "Your check is dubious...why would you expect null != null?", 180 expectedResult); 181 return; 182 } 183 184 if ((lhs == null) || (rhs == null)) { 185 Assert.assertFalse( 186 "Your check is dubious...why would you expect an object " 187 + "to be equal to null?", expectedResult); 188 } 189 190 if (lhs != null) { 191 assertEquals(expectedResult, lhs.equals(rhs)); 192 } 193 if (rhs != null) { 194 assertEquals(expectedResult, rhs.equals(lhs)); 195 } 196 197 if (expectedResult) { 198 String hashMessage = 199 "hashCode() values for equal objects should be the same"; 200 Assert.assertTrue(hashMessage, lhs.hashCode() == rhs.hashCode()); 201 } 202 } 203 } 204