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