| /* |
| * Copyright 2006 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.google.common.geometry; |
| |
| import com.google.common.collect.ImmutableList; |
| |
| /** |
| * Tests for {@link S2EdgeUtil}. |
| * |
| */ |
| public strictfp class S2EdgeUtilTest extends GeometryTestCase { |
| |
| public static final int DEGENERATE = -2; |
| |
| private void compareResult(int actual, int expected) { |
| // HACK ALERT: RobustCrossing() is allowed to return 0 or -1 if either edge |
| // is degenerate. We use the value kDegen to represent this possibility. |
| if (expected == DEGENERATE) { |
| assertTrue(actual <= 0); |
| } else { |
| assertEquals(expected, actual); |
| } |
| } |
| |
| private void assertCrossing(S2Point a, |
| S2Point b, |
| S2Point c, |
| S2Point d, |
| int robust, |
| boolean edgeOrVertex, |
| boolean simple) { |
| a = S2Point.normalize(a); |
| b = S2Point.normalize(b); |
| c = S2Point.normalize(c); |
| d = S2Point.normalize(d); |
| |
| compareResult(S2EdgeUtil.robustCrossing(a, b, c, d), robust); |
| if (simple) { |
| assertEquals(robust > 0, S2EdgeUtil.simpleCrossing(a, b, c, d)); |
| } |
| S2EdgeUtil.EdgeCrosser crosser = new S2EdgeUtil.EdgeCrosser(a, b, c); |
| compareResult(crosser.robustCrossing(d), robust); |
| compareResult(crosser.robustCrossing(c), robust); |
| |
| assertEquals(S2EdgeUtil.edgeOrVertexCrossing(a, b, c, d), edgeOrVertex); |
| assertEquals(edgeOrVertex, crosser.edgeOrVertexCrossing(d)); |
| assertEquals(edgeOrVertex, crosser.edgeOrVertexCrossing(c)); |
| } |
| |
| private void assertCrossings(S2Point a, |
| S2Point b, |
| S2Point c, |
| S2Point d, |
| int robust, |
| boolean edgeOrVertex, |
| boolean simple) { |
| assertCrossing(a, b, c, d, robust, edgeOrVertex, simple); |
| assertCrossing(b, a, c, d, robust, edgeOrVertex, simple); |
| assertCrossing(a, b, d, c, robust, edgeOrVertex, simple); |
| assertCrossing(b, a, d, c, robust, edgeOrVertex, simple); |
| assertCrossing(a, a, c, d, DEGENERATE, false, false); |
| assertCrossing(a, b, c, c, DEGENERATE, false, false); |
| assertCrossing(a, b, a, b, 0, true, false); |
| assertCrossing(c, d, a, b, robust, (edgeOrVertex ^ (robust == 0)), simple); |
| } |
| |
| public void testCrossings() { |
| // The real tests of edge crossings are in s2{loop,polygon}_unittest, |
| // but we do a few simple tests here. |
| |
| // Two regular edges that cross. |
| assertCrossings(new S2Point(1, 2, 1), |
| new S2Point(1, -3, 0.5), |
| new S2Point(1, -0.5, -3), |
| new S2Point(0.1, 0.5, 3), |
| 1, |
| true, |
| true); |
| |
| // Two regular edges that cross antipodal points. |
| assertCrossings(new S2Point(1, 2, 1), |
| new S2Point(1, -3, 0.5), |
| new S2Point(-1, 0.5, 3), |
| new S2Point(-0.1, -0.5, -3), |
| -1, |
| false, |
| true); |
| |
| // Two edges on the same great circle. |
| assertCrossings(new S2Point(0, 0, -1), |
| new S2Point(0, 1, 0), |
| new S2Point(0, 1, 1), |
| new S2Point(0, 0, 1), |
| -1, |
| false, |
| true); |
| |
| // Two edges that cross where one vertex is S2.Origin(). |
| assertCrossings(new S2Point(1, 0, 0), |
| new S2Point(0, 1, 0), |
| new S2Point(0, 0, 1), |
| new S2Point(1, 1, -1), |
| 1, |
| true, |
| true); |
| |
| // Two edges that cross antipodal points where one vertex is S2.Origin(). |
| assertCrossings(new S2Point(1, 0, 0), |
| new S2Point(0, 1, 0), |
| new S2Point(0, 0, -1), |
| new S2Point(-1, -1, 1), |
| -1, |
| false, |
| true); |
| |
| // Two edges that share an endpoint. The Ortho() direction is (-4,0,2), |
| // and edge CD is further CCW around (2,3,4) than AB. |
| assertCrossings(new S2Point(2, 3, 4), |
| new S2Point(-1, 2, 5), |
| new S2Point(7, -2, 3), |
| new S2Point(2, 3, 4), |
| 0, |
| false, |
| true); |
| |
| // Two edges that barely cross edge other. |
| assertCrossings(new S2Point(1, 1, 1), |
| new S2Point(1, 1 - 1e-15, -1), |
| new S2Point(-1, -1, 0), |
| new S2Point(1, 1, 0), |
| 1, |
| true, |
| false); |
| } |
| |
| private S2LatLngRect getEdgeBound(double x1, |
| double y1, |
| double z1, |
| double x2, |
| double y2, |
| double z2) { |
| S2EdgeUtil.RectBounder bounder = new S2EdgeUtil.RectBounder(); |
| S2Point p1 = S2Point.normalize(new S2Point(x1, y1, z1)); |
| S2Point p2 = S2Point.normalize(new S2Point(x2, y2, z2)); |
| bounder.addPoint(p1); |
| bounder.addPoint(p2); |
| return bounder.getBound(); |
| } |
| |
| public void testRectBounder() { |
| // Check cases where min/max latitude is not at a vertex. |
| // Max, CW |
| assertDoubleNear(getEdgeBound(1, 1, 1, 1, -1, 1).lat().hi(), S2.M_PI_4); |
| // Max, CCW |
| assertDoubleNear(getEdgeBound(1, -1, 1, 1, 1, 1).lat().hi(), S2.M_PI_4); |
| // Min, CW |
| assertDoubleNear(getEdgeBound(1, -1, -1, -1, -1, -1).lat().lo(), -S2.M_PI_4); |
| // Min, CCW |
| assertDoubleNear(getEdgeBound(-1, 1, -1, -1, -1, -1).lat().lo(), -S2.M_PI_4); |
| |
| // Check cases where the edge passes through one of the poles. |
| assertDoubleNear(getEdgeBound(.3, .4, 1, -.3, -.4, 1).lat().hi(), S2.M_PI_2); |
| assertDoubleNear(getEdgeBound(.3, .4, -1, -.3, -.4, -1).lat().lo(), -S2.M_PI_2); |
| |
| // Check cases where the min/max latitude is attained at a vertex. |
| double kCubeLat = Math.asin(Math.sqrt(1. / 3)); // 35.26 degrees |
| assertTrue( |
| getEdgeBound(1, 1, 1, 1, -1, -1).lat().approxEquals(new R1Interval(-kCubeLat, kCubeLat))); |
| assertTrue( |
| getEdgeBound(1, -1, 1, 1, 1, -1).lat().approxEquals(new R1Interval(-kCubeLat, kCubeLat))); |
| } |
| |
| // Produce a normalized S2Point for testing. |
| private S2Point S2NP(double x, double y, double z) { |
| return S2Point.normalize(new S2Point(x, y, z)); |
| } |
| |
| public void testXYZPruner() { |
| S2EdgeUtil.XYZPruner pruner = new S2EdgeUtil.XYZPruner(); |
| |
| // We aren't actually normalizing these points but it doesn't |
| // matter too much as long as we are reasonably close to unit vectors. |
| // This is a simple triangle on the equator. |
| pruner.addEdgeToBounds(S2NP(0, 1, 0), S2NP(0.1, 1, 0)); |
| pruner.addEdgeToBounds(S2NP(0.1, 1, 0), S2NP(0.1, 1, 0.1)); |
| pruner.addEdgeToBounds(S2NP(0.1, 1, 0.1), S2NP(0, 1, 0)); |
| |
| // try a loop around the triangle but far enough out to not overlap. |
| pruner.setFirstIntersectPoint(S2NP(-0.1, 1.0, 0.0)); |
| assertFalse(pruner.intersects(S2NP(-0.1, 1.0, 0.2))); |
| assertFalse(pruner.intersects(S2NP(0.0, 1.0, 0.2))); |
| assertFalse(pruner.intersects(S2NP(0.2, 1.0, 0.2))); |
| assertFalse(pruner.intersects(S2NP(0.2, 1.0, 0.05))); |
| assertFalse(pruner.intersects(S2NP(0.2, 1.0, -0.1))); |
| assertFalse(pruner.intersects(S2NP(-0.1, 1.0, -0.1))); |
| assertFalse(pruner.intersects(S2NP(-0.1, 1.0, 0.0))); |
| |
| // now we go to a point in the bounding box of the triangle but well |
| // out of the loop. This will be a hit even though it really does not |
| // need to be. |
| assertTrue(pruner.intersects(S2NP(0.02, 1.0, 0.04))); |
| |
| // now we zoom out to do an edge *just* below the triangle. This should |
| // be a hit because we are within the deformation zone. |
| assertTrue(pruner.intersects(S2NP(-0.1, 1.0, -0.03))); |
| assertFalse(pruner.intersects(S2NP(0.05, 1.0, -0.03))); // not close |
| assertTrue(pruner.intersects(S2NP(0.05, 1.0, -0.01))); // close |
| assertTrue(pruner.intersects(S2NP(0.05, 1.0, 0.13))); |
| assertFalse(pruner.intersects(S2NP(0.13, 1.0, 0.14))); |
| |
| // Create a new pruner with very small area and correspondingly narrow |
| // deformation tolerances. |
| S2EdgeUtil.XYZPruner spruner = new S2EdgeUtil.XYZPruner(); |
| spruner.addEdgeToBounds(S2NP(0, 1, 0.000), S2NP(0.001, 1, 0)); |
| spruner.addEdgeToBounds(S2NP(0.001, 1, 0.000), S2NP(0.001, 1, 0.001)); |
| spruner.addEdgeToBounds(S2NP(0.001, 1, 0.001), S2NP(0.000, 1, 0)); |
| |
| spruner.setFirstIntersectPoint(S2NP(0, 1.0, -0.1)); |
| assertFalse(spruner.intersects(S2NP(0.0005, 1.0, -0.0005))); |
| assertFalse(spruner.intersects(S2NP(0.0005, 1.0, -0.0005))); |
| assertFalse(spruner.intersects(S2NP(0.0005, 1.0, -0.00001))); |
| assertTrue(spruner.intersects(S2NP(0.0005, 1.0, -0.0000001))); |
| } |
| |
| public void testLongitudePruner() { |
| S2EdgeUtil.LongitudePruner pruner1 = new S2EdgeUtil.LongitudePruner( |
| new S1Interval(0.75 * S2.M_PI, -0.75 * S2.M_PI), new S2Point(0, 1, 2)); |
| |
| assertFalse(pruner1.intersects(new S2Point(1, 1, 3))); |
| assertTrue(pruner1.intersects(new S2Point(-1 - 1e-15, -1, 0))); |
| assertTrue(pruner1.intersects(new S2Point(-1, 0, 0))); |
| assertTrue(pruner1.intersects(new S2Point(-1, 0, 0))); |
| assertTrue(pruner1.intersects(new S2Point(1, -1, 8))); |
| assertFalse(pruner1.intersects(new S2Point(1, 0, -2))); |
| assertTrue(pruner1.intersects(new S2Point(-1, -1e-15, 0))); |
| |
| S2EdgeUtil.LongitudePruner pruner2 = new S2EdgeUtil.LongitudePruner( |
| new S1Interval(0.25 * S2.M_PI, 0.25 * S2.M_PI), new S2Point(1, 0, 0)); |
| |
| assertFalse(pruner2.intersects(new S2Point(2, 1, 2))); |
| assertTrue(pruner2.intersects(new S2Point(1, 2, 3))); |
| assertFalse(pruner2.intersects(new S2Point(0, 1, 4))); |
| assertFalse(pruner2.intersects(new S2Point(-1e-15, -1, -1))); |
| } |
| |
| private void assertWedge(S2Point a0, |
| S2Point ab1, |
| S2Point a2, |
| S2Point b0, |
| S2Point b2, |
| boolean contains, |
| boolean intersects, |
| boolean crosses) { |
| a0 = S2Point.normalize(a0); |
| ab1 = S2Point.normalize(ab1); |
| a2 = S2Point.normalize(a2); |
| b0 = S2Point.normalize(b0); |
| b2 = S2Point.normalize(b2); |
| |
| assertEquals(new S2EdgeUtil.WedgeContains().test(a0, ab1, a2, b0, b2), contains ? 1 : 0); |
| assertEquals(new S2EdgeUtil.WedgeIntersects().test(a0, ab1, a2, b0, b2), intersects ? -1 : 0); |
| assertEquals(new S2EdgeUtil.WedgeContainsOrIntersects().test(a0, ab1, a2, b0, b2), |
| contains ? 1 : intersects ? -1 : 0); |
| assertEquals(new S2EdgeUtil.WedgeContainsOrCrosses().test(a0, ab1, a2, b0, b2), |
| contains ? 1 : crosses ? -1 : 0); |
| } |
| |
| public void testWedges() { |
| // For simplicity, all of these tests use an origin of (0, 0, 1). |
| // This shouldn't matter as long as the lower-level primitives are |
| // implemented correctly. |
| |
| // Intersection in one wedge. |
| assertWedge(new S2Point(-1, 0, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(1, 2, 10), |
| new S2Point(0, 1, 10), |
| new S2Point(1, -2, 10), |
| false, |
| true, |
| true); |
| // Intersection in two wedges. |
| assertWedge(new S2Point(-1, -1, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(1, -1, 10), |
| new S2Point(1, 0, 10), |
| new S2Point(-1, 1, 10), |
| false, |
| true, |
| true); |
| |
| // Normal containment. |
| assertWedge(new S2Point(-1, -1, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(1, -1, 10), |
| new S2Point(-1, 0, 10), |
| new S2Point(1, 0, 10), |
| true, |
| true, |
| false); |
| // Containment with equality on one side. |
| assertWedge(new S2Point(2, 1, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(-1, -1, 10), |
| new S2Point(2, 1, 10), |
| new S2Point(1, -5, 10), |
| true, |
| true, |
| false); |
| // Containment with equality on the other side. |
| assertWedge(new S2Point(2, 1, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(-1, -1, 10), |
| new S2Point(1, -2, 10), |
| new S2Point(-1, -1, 10), |
| true, |
| true, |
| false); |
| // Containment with equality on both sides. |
| assertWedge(new S2Point(-2, 3, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(4, -5, 10), |
| new S2Point(-2, 3, 10), |
| new S2Point(4, -5, 10), |
| true, |
| true, |
| false); |
| |
| // Disjoint with equality on one side. |
| assertWedge(new S2Point(-2, 3, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(4, -5, 10), |
| new S2Point(4, -5, 10), |
| new S2Point(-2, -3, 10), |
| false, |
| false, |
| false); |
| // Disjoint with equality on the other side. |
| assertWedge(new S2Point(-2, 3, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(0, 5, 10), |
| new S2Point(4, -5, 10), |
| new S2Point(-2, 3, 10), |
| false, |
| false, |
| false); |
| // Disjoint with equality on both sides. |
| assertWedge(new S2Point(-2, 3, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(4, -5, 10), |
| new S2Point(4, -5, 10), |
| new S2Point(-2, 3, 10), |
| false, |
| false, |
| false); |
| |
| // B contains A with equality on one side. |
| assertWedge(new S2Point(2, 1, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(1, -5, 10), |
| new S2Point(2, 1, 10), |
| new S2Point(-1, -1, 10), |
| false, |
| true, |
| false); |
| // B contains A with equality on the other side. |
| assertWedge(new S2Point(2, 1, 10), |
| new S2Point(0, 0, 1), |
| new S2Point(1, -5, 10), |
| new S2Point(-2, 1, 10), |
| new S2Point(1, -5, 10), |
| false, |
| true, |
| false); |
| } |
| |
| public void testGetClosestPoint() { |
| final double kMargin = 1e-6; |
| |
| S2Point a = S2LatLng.fromDegrees(-0.5, 0).toPoint(); |
| S2Point b = S2LatLng.fromDegrees(+0.5, 0).toPoint(); |
| |
| // On edge at end points. |
| assertEquals(a, S2EdgeUtil.getClosestPoint(a, a, b)); |
| assertEquals(b, S2EdgeUtil.getClosestPoint(b, a, b)); |
| |
| // On edge in between. |
| S2Point mid = S2LatLng.fromDegrees(0, 0).toPoint(); |
| assertEquals(mid, S2EdgeUtil.getClosestPoint(mid, a, b)); |
| |
| // End points are closest |
| assertEquals(a, S2EdgeUtil.getClosestPoint(S2LatLng.fromDegrees(-1, 0).toPoint(), a, b)); |
| assertEquals(b, S2EdgeUtil.getClosestPoint(S2LatLng.fromDegrees(+1, 0).toPoint(), a, b)); |
| |
| // Intermediate point is closest. |
| S2Point x = S2LatLng.fromDegrees(+0.1, 1).toPoint(); |
| S2Point expectedClosestPoint = S2LatLng.fromDegrees(+0.1, 0).toPoint(); |
| |
| assertTrue(expectedClosestPoint.aequal(S2EdgeUtil.getClosestPoint(x, a, b), kMargin)); |
| } |
| |
| // Given a point X and an edge AB, check that the distance from X to AB is |
| // "distanceRadians" and the closest point on AB is "expectedClosest". |
| private static void checkDistance( |
| S2Point x, S2Point a, S2Point b, double distanceRadians, S2Point expectedClosest) { |
| final double kEpsilon = 1e-10; |
| x = S2Point.normalize(x); |
| a = S2Point.normalize(a); |
| b = S2Point.normalize(b); |
| expectedClosest = S2Point.normalize(expectedClosest); |
| |
| assertEquals(distanceRadians, S2EdgeUtil.getDistance(x, a, b).radians(), kEpsilon); |
| |
| S2Point closest = S2EdgeUtil.getClosestPoint(x, a, b); |
| if (expectedClosest.equals(new S2Point(0, 0, 0))) { |
| // This special value says that the result should be A or B. |
| assertTrue(closest == a || closest == b); |
| } else { |
| assertTrue(S2.approxEquals(closest, expectedClosest)); |
| } |
| } |
| |
| public void testGetDistance() { |
| checkDistance( |
| new S2Point(1, 0, 0), new S2Point(1, 0, 0), new S2Point(0, 1, 0), 0, new S2Point(1, 0, 0)); |
| checkDistance( |
| new S2Point(0, 1, 0), new S2Point(1, 0, 0), new S2Point(0, 1, 0), 0, new S2Point(0, 1, 0)); |
| checkDistance( |
| new S2Point(1, 3, 0), new S2Point(1, 0, 0), new S2Point(0, 1, 0), 0, new S2Point(1, 3, 0)); |
| checkDistance(new S2Point(0, 0, 1), new S2Point(1, 0, 0), new S2Point(0, 1, 0), Math.PI / 2, |
| new S2Point(1, 0, 0)); |
| checkDistance(new S2Point(0, 0, -1), new S2Point(1, 0, 0), new S2Point(0, 1, 0), Math.PI / 2, |
| new S2Point(1, 0, 0)); |
| checkDistance(new S2Point(-1, -1, 0), new S2Point(1, 0, 0), new S2Point(0, 1, 0), |
| 0.75 * Math.PI, new S2Point(0, 0, 0)); |
| checkDistance(new S2Point(0, 1, 0), new S2Point(1, 0, 0), new S2Point(1, 1, 0), Math.PI / 4, |
| new S2Point(1, 1, 0)); |
| checkDistance(new S2Point(0, -1, 0), new S2Point(1, 0, 0), new S2Point(1, 1, 0), Math.PI / 2, |
| new S2Point(1, 0, 0)); |
| checkDistance(new S2Point(0, -1, 0), new S2Point(1, 0, 0), new S2Point(-1, 1, 0), Math.PI / 2, |
| new S2Point(1, 0, 0)); |
| checkDistance(new S2Point(-1, -1, 0), new S2Point(1, 0, 0), new S2Point(-1, 1, 0), Math.PI / 2, |
| new S2Point(-1, 1, 0)); |
| checkDistance(new S2Point(1, 1, 1), new S2Point(1, 0, 0), new S2Point(0, 1, 0), |
| Math.asin(Math.sqrt(1. / 3)), new S2Point(1, 1, 0)); |
| checkDistance(new S2Point(1, 1, -1), new S2Point(1, 0, 0), new S2Point(0, 1, 0), |
| Math.asin(Math.sqrt(1. / 3)), new S2Point(1, 1, 0)); |
| checkDistance(new S2Point(-1, 0, 0), new S2Point(1, 1, 0), new S2Point(1, 1, 0), 0.75 * Math.PI, |
| new S2Point(1, 1, 0)); |
| checkDistance(new S2Point(0, 0, -1), new S2Point(1, 1, 0), new S2Point(1, 1, 0), Math.PI / 2, |
| new S2Point(1, 1, 0)); |
| checkDistance(new S2Point(-1, 0, 0), new S2Point(1, 0, 0), new S2Point(1, 0, 0), Math.PI, |
| new S2Point(1, 0, 0)); |
| } |
| |
| public void testIntersectionTolerance() { |
| // We repeatedly construct two edges that cross near a random point "p", |
| // and measure the distance from the actual intersection point "x" to the |
| // the expected intersection point "p" and also to the edges that cross |
| // near "p". |
| // |
| // Note that getIntersection() does not guarantee that "x" and "p" will be |
| // close together (since the intersection point is numerically unstable |
| // when the edges cross at a very small angle), but it does guarantee that |
| // "x" will be close to both of the edges that cross. |
| S1Angle maxPointDist = new S1Angle(); |
| S1Angle maxEdgeDist = new S1Angle(); |
| |
| for (int i = 0; i < 1000; ++i) { |
| // We construct two edges AB and CD that intersect near "p". The angle |
| // between AB and CD (expressed as a slope) is chosen randomly between |
| // 1e-15 and 1.0 such that its logarithm is uniformly distributed. This |
| // implies that small values are much more likely to be chosen. |
| // |
| // Once the slope is chosen, the four points ABCD must be offset from P |
| // by at least (1e-15 / slope) so that the points are guaranteed to have |
| // the correct circular ordering around P. This is the distance from P |
| // at which the two edges are separated by about 1e-15, which is |
| // approximately the minimum distance at which we can expect computed |
| // points on the two lines to be distinct and have the correct ordering. |
| // |
| // The actual offset distance from P is chosen randomly in the range |
| // [1e-15 / slope, 1.0], again uniformly distributing the logarithm. |
| // This ensures that we test both long and very short segments that |
| // intersect at both large and very small angles. |
| |
| ImmutableList<S2Point> points = getRandomFrame(); |
| S2Point p = points.get(0); |
| S2Point d1 = points.get(1); |
| S2Point d2 = points.get(2); |
| double slope = Math.pow(1e-15, rand.nextDouble()); |
| d2 = S2Point.add(d1, S2Point.mul(d2, slope)); |
| S2Point a = S2Point.normalize( |
| S2Point.add(p, S2Point.mul(d1, Math.pow(1e-15 / slope, rand.nextDouble())))); |
| S2Point b = S2Point.normalize( |
| S2Point.sub(p, S2Point.mul(d1, Math.pow(1e-15 / slope, rand.nextDouble())))); |
| S2Point c = S2Point.normalize( |
| S2Point.add(p, S2Point.mul(d2, Math.pow(1e-15 / slope, rand.nextDouble())))); |
| S2Point d = S2Point.normalize( |
| S2Point.sub(p, S2Point.mul(d2, Math.pow(1e-15 / slope, rand.nextDouble())))); |
| S2Point x = S2EdgeUtil.getIntersection(a, b, c, d); |
| S1Angle distAb = S2EdgeUtil.getDistance(x, a, b); |
| S1Angle distCd = S2EdgeUtil.getDistance(x, c, d); |
| |
| assertTrue(distAb.lessThan(S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE)); |
| assertTrue(distCd.lessThan(S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE)); |
| |
| // test getIntersection() post conditions |
| assertTrue(S2.orderedCCW(a, x, b, S2Point.normalize(S2.robustCrossProd(a, b)))); |
| assertTrue(S2.orderedCCW(c, x, d, S2Point.normalize(S2.robustCrossProd(c, d)))); |
| |
| maxEdgeDist = S1Angle.max(maxEdgeDist, S1Angle.max(distAb, distCd)); |
| maxPointDist = S1Angle.max(maxPointDist, new S1Angle(p, x)); |
| } |
| } |
| } |
