You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
531 lines
20 KiB
531 lines
20 KiB
/*
|
|
* 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));
|
|
}
|
|
}
|
|
}
|