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.
323 lines
13 KiB
323 lines
13 KiB
/*
|
|
* Copyright 2005 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 java.util.logging.Logger;
|
|
|
|
public strictfp class S2Test extends GeometryTestCase {
|
|
|
|
private static Logger logger = Logger.getLogger(S2Test.class.getName());
|
|
|
|
// Test helper methods for testing the traversal order.
|
|
private static int swapAxes(int ij) {
|
|
return ((ij >> 1) & 1) + ((ij & 1) << 1);
|
|
}
|
|
|
|
private static int invertBits(int ij) {
|
|
return ij ^ 3;
|
|
}
|
|
|
|
public void testTraversalOrder() {
|
|
for (int r = 0; r < 4; ++r) {
|
|
for (int i = 0; i < 4; ++i) {
|
|
// Check consistency with respect to swapping axes.
|
|
assertEquals(S2.ijToPos(r, i),
|
|
S2.ijToPos(r ^ S2.SWAP_MASK, swapAxes(i)));
|
|
assertEquals(S2.posToIJ(r, i),
|
|
swapAxes(S2.posToIJ(r ^ S2.SWAP_MASK, i)));
|
|
|
|
// Check consistency with respect to reversing axis directions.
|
|
assertEquals(S2.ijToPos(r, i),
|
|
S2.ijToPos(r ^ S2.INVERT_MASK, invertBits(i)));
|
|
assertEquals(S2.posToIJ(r, i),
|
|
invertBits(S2.posToIJ(r ^ S2.INVERT_MASK, i)));
|
|
|
|
// Check that the two tables are inverses of each other.
|
|
assertEquals(S2.ijToPos(r, S2.posToIJ(r, i)), i);
|
|
assertEquals(S2.posToIJ(r, S2.ijToPos(r, i)), i);
|
|
}
|
|
}
|
|
}
|
|
|
|
public void testSTUV() {
|
|
// Check boundary conditions.
|
|
for (double x = -1; x <= 1; ++x) {
|
|
assertEquals(S2Projections.stToUV(x), x);
|
|
assertEquals(S2Projections.uvToST(x), x);
|
|
}
|
|
// Check that UVtoST and STtoUV are inverses.
|
|
for (double x = -1; x <= 1; x += 0.0001) {
|
|
assertDoubleNear(S2Projections.uvToST(S2Projections.stToUV(x)), x);
|
|
assertDoubleNear(S2Projections.stToUV(S2Projections.uvToST(x)), x);
|
|
}
|
|
}
|
|
|
|
public void testFaceUVtoXYZ() {
|
|
// Check that each face appears exactly once.
|
|
S2Point sum = new S2Point();
|
|
for (int face = 0; face < 6; ++face) {
|
|
S2Point center = S2Projections.faceUvToXyz(face, 0, 0);
|
|
assertEquals(S2Projections.getNorm(face), center);
|
|
assertEquals(Math.abs(center.get(center.largestAbsComponent())), 1.0);
|
|
sum = S2Point.add(sum, S2Point.fabs(center));
|
|
}
|
|
assertEquals(sum, new S2Point(2, 2, 2));
|
|
|
|
// Check that each face has a right-handed coordinate system.
|
|
for (int face = 0; face < 6; ++face) {
|
|
assertEquals(
|
|
S2Point.crossProd(S2Projections.getUAxis(face), S2Projections.getVAxis(face)).dotProd(
|
|
S2Projections.faceUvToXyz(face, 0, 0)), 1.0);
|
|
}
|
|
|
|
// Check that the Hilbert curves on each face combine to form a
|
|
// continuous curve over the entire cube.
|
|
for (int face = 0; face < 6; ++face) {
|
|
// The Hilbert curve on each face starts at (-1,-1) and terminates
|
|
// at either (1,-1) (if axes not swapped) or (-1,1) (if swapped).
|
|
int sign = ((face & S2.SWAP_MASK) != 0) ? -1 : 1;
|
|
assertEquals(S2Projections.faceUvToXyz(face, sign, -sign),
|
|
S2Projections.faceUvToXyz((face + 1) % 6, -1, -1));
|
|
}
|
|
}
|
|
|
|
public void testUVNorms() {
|
|
// Check that GetUNorm and GetVNorm compute right-handed normals for
|
|
// an edge in the increasing U or V direction.
|
|
for (int face = 0; face < 6; ++face) {
|
|
for (double x = -1; x <= 1; x += 1 / 1024.) {
|
|
assertDoubleNear(
|
|
S2Point.crossProd(
|
|
S2Projections.faceUvToXyz(face, x, -1), S2Projections.faceUvToXyz(face, x, 1))
|
|
.angle(S2Projections.getUNorm(face, x)), 0);
|
|
assertDoubleNear(
|
|
S2Point.crossProd(
|
|
S2Projections.faceUvToXyz(face, -1, x), S2Projections.faceUvToXyz(face, 1, x))
|
|
.angle(S2Projections.getVNorm(face, x)), 0);
|
|
}
|
|
}
|
|
}
|
|
|
|
public void testUVAxes() {
|
|
// Check that axes are consistent with FaceUVtoXYZ.
|
|
for (int face = 0; face < 6; ++face) {
|
|
assertEquals(S2Projections.getUAxis(face), S2Point.sub(
|
|
S2Projections.faceUvToXyz(face, 1, 0), S2Projections.faceUvToXyz(face, 0, 0)));
|
|
assertEquals(S2Projections.getVAxis(face), S2Point.sub(
|
|
S2Projections.faceUvToXyz(face, 0, 1), S2Projections.faceUvToXyz(face, 0, 0)));
|
|
}
|
|
}
|
|
|
|
public void testAngleArea() {
|
|
S2Point pz = new S2Point(0, 0, 1);
|
|
S2Point p000 = new S2Point(1, 0, 0);
|
|
S2Point p045 = new S2Point(1, 1, 0);
|
|
S2Point p090 = new S2Point(0, 1, 0);
|
|
S2Point p180 = new S2Point(-1, 0, 0);
|
|
assertDoubleNear(S2.angle(p000, pz, p045), S2.M_PI_4);
|
|
assertDoubleNear(S2.angle(p045, pz, p180), 3 * S2.M_PI_4);
|
|
assertDoubleNear(S2.angle(p000, pz, p180), S2.M_PI);
|
|
assertDoubleNear(S2.angle(pz, p000, pz), 0);
|
|
assertDoubleNear(S2.angle(pz, p000, p045), S2.M_PI_2);
|
|
|
|
assertDoubleNear(S2.area(p000, p090, pz), S2.M_PI_2);
|
|
assertDoubleNear(S2.area(p045, pz, p180), 3 * S2.M_PI_4);
|
|
|
|
// Make sure that area() has good *relative* accuracy even for
|
|
// very small areas.
|
|
final double eps = 1e-10;
|
|
S2Point pepsx = new S2Point(eps, 0, 1);
|
|
S2Point pepsy = new S2Point(0, eps, 1);
|
|
double expected1 = 0.5 * eps * eps;
|
|
assertDoubleNear(S2.area(pepsx, pepsy, pz), expected1, 1e-14 * expected1);
|
|
|
|
// Make sure that it can handle degenerate triangles.
|
|
S2Point pr = new S2Point(0.257, -0.5723, 0.112);
|
|
S2Point pq = new S2Point(-0.747, 0.401, 0.2235);
|
|
assertEquals(S2.area(pr, pr, pr), 0.0);
|
|
// TODO: The following test is not exact in optimized mode because the
|
|
// compiler chooses to mix 64-bit and 80-bit intermediate results.
|
|
assertDoubleNear(S2.area(pr, pq, pr), 0);
|
|
assertEquals(S2.area(p000, p045, p090), 0.0);
|
|
|
|
double maxGirard = 0;
|
|
for (int i = 0; i < 10000; ++i) {
|
|
S2Point p0 = randomPoint();
|
|
S2Point d1 = randomPoint();
|
|
S2Point d2 = randomPoint();
|
|
S2Point p1 = S2Point.add(p0, S2Point.mul(d1, 1e-15));
|
|
S2Point p2 = S2Point.add(p0, S2Point.mul(d2, 1e-15));
|
|
// The actual displacement can be as much as 1.2e-15 due to roundoff.
|
|
// This yields a maximum triangle area of about 0.7e-30.
|
|
assertTrue(S2.area(p0, p1, p2) < 0.7e-30);
|
|
maxGirard = Math.max(maxGirard, S2.girardArea(p0, p1, p2));
|
|
}
|
|
logger.info("Worst case Girard for triangle area 1e-30: " + maxGirard);
|
|
|
|
// Try a very long and skinny triangle.
|
|
S2Point p045eps = new S2Point(1, 1, eps);
|
|
double expected2 = 5.8578643762690495119753e-11; // Mathematica.
|
|
assertDoubleNear(S2.area(p000, p045eps, p090), expected2, 1e-9 * expected2);
|
|
|
|
// Triangles with near-180 degree edges that sum to a quarter-sphere.
|
|
final double eps2 = 1e-10;
|
|
S2Point p000eps2 = new S2Point(1, 0.1 * eps2, eps2);
|
|
double quarterArea1 =
|
|
S2.area(p000eps2, p000, p090) + S2.area(p000eps2, p090, p180) + S2.area(p000eps2, p180, pz)
|
|
+ S2.area(p000eps2, pz, p000);
|
|
assertDoubleNear(quarterArea1, S2.M_PI);
|
|
|
|
// Four other triangles that sum to a quarter-sphere.
|
|
S2Point p045eps2 = new S2Point(1, 1, eps2);
|
|
double quarterArea2 =
|
|
S2.area(p045eps2, p000, p090) + S2.area(p045eps2, p090, p180) + S2.area(p045eps2, p180, pz)
|
|
+ S2.area(p045eps2, pz, p000);
|
|
assertDoubleNear(quarterArea2, S2.M_PI);
|
|
}
|
|
|
|
public void testCCW() {
|
|
S2Point a = new S2Point(0.72571927877036835, 0.46058825605889098, 0.51106749730504852);
|
|
S2Point b = new S2Point(0.7257192746638208, 0.46058826573818168, 0.51106749441312738);
|
|
S2Point c = new S2Point(0.72571927671709457, 0.46058826089853633, 0.51106749585908795);
|
|
assertTrue(S2.robustCCW(a, b, c) != 0);
|
|
}
|
|
|
|
// Note: obviously, I could have defined a bundle of metrics like this in the
|
|
// S2 class itself rather than just for testing. However, it's not clear that
|
|
// this is useful other than for testing purposes, and I find
|
|
// S2.kMinWidth.GetMaxLevel(width) to be slightly more readable than
|
|
// than S2.kWidth.min().GetMaxLevel(width). Also, there is no fundamental
|
|
// reason that we need to analyze the minimum, maximum, and average values of
|
|
// every metric; it would be perfectly reasonable to just define one of these.
|
|
|
|
class MetricBundle {
|
|
public MetricBundle(S2.Metric min, S2.Metric max, S2.Metric avg) {
|
|
this.min_ = min;
|
|
this.max_ = max;
|
|
this.avg_ = avg;
|
|
}
|
|
|
|
S2.Metric min_;
|
|
S2.Metric max_;
|
|
S2.Metric avg_;
|
|
}
|
|
|
|
public void testMinMaxAvg(MetricBundle bundle) {
|
|
assertTrue(bundle.min_.deriv() < bundle.avg_.deriv());
|
|
assertTrue(bundle.avg_.deriv() < bundle.max_.deriv());
|
|
}
|
|
|
|
public void testLessOrEqual(MetricBundle a, MetricBundle b) {
|
|
assertTrue(a.min_.deriv() <= b.min_.deriv());
|
|
assertTrue(a.max_.deriv() <= b.max_.deriv());
|
|
assertTrue(a.avg_.deriv() <= b.avg_.deriv());
|
|
}
|
|
|
|
public void testMetrics() {
|
|
|
|
MetricBundle angleSpan = new MetricBundle(
|
|
S2Projections.MIN_ANGLE_SPAN, S2Projections.MAX_ANGLE_SPAN, S2Projections.AVG_ANGLE_SPAN);
|
|
MetricBundle width =
|
|
new MetricBundle(S2Projections.MIN_WIDTH, S2Projections.MAX_WIDTH, S2Projections.AVG_WIDTH);
|
|
MetricBundle edge =
|
|
new MetricBundle(S2Projections.MIN_EDGE, S2Projections.MAX_EDGE, S2Projections.AVG_EDGE);
|
|
MetricBundle diag =
|
|
new MetricBundle(S2Projections.MIN_DIAG, S2Projections.MAX_DIAG, S2Projections.AVG_DIAG);
|
|
MetricBundle area =
|
|
new MetricBundle(S2Projections.MIN_AREA, S2Projections.MAX_AREA, S2Projections.AVG_AREA);
|
|
|
|
// First, check that min <= avg <= max for each metric.
|
|
testMinMaxAvg(angleSpan);
|
|
testMinMaxAvg(width);
|
|
testMinMaxAvg(edge);
|
|
testMinMaxAvg(diag);
|
|
testMinMaxAvg(area);
|
|
|
|
// Check that the maximum aspect ratio of an individual cell is consistent
|
|
// with the global minimums and maximums.
|
|
assertTrue(S2Projections.MAX_EDGE_ASPECT >= 1.0);
|
|
assertTrue(S2Projections.MAX_EDGE_ASPECT
|
|
< S2Projections.MAX_EDGE.deriv() / S2Projections.MIN_EDGE.deriv());
|
|
assertTrue(S2Projections.MAX_DIAG_ASPECT >= 1);
|
|
assertTrue(S2Projections.MAX_DIAG_ASPECT
|
|
< S2Projections.MAX_DIAG.deriv() / S2Projections.MIN_DIAG.deriv());
|
|
|
|
// Check various conditions that are provable mathematically.
|
|
testLessOrEqual(width, angleSpan);
|
|
testLessOrEqual(width, edge);
|
|
testLessOrEqual(edge, diag);
|
|
|
|
assertTrue(S2Projections.MIN_AREA.deriv()
|
|
>= S2Projections.MIN_WIDTH.deriv() * S2Projections.MIN_EDGE.deriv() - 1e-15);
|
|
assertTrue(S2Projections.MAX_AREA.deriv()
|
|
< S2Projections.MAX_WIDTH.deriv() * S2Projections.MAX_EDGE.deriv() + 1e-15);
|
|
|
|
// GetMinLevelForLength() and friends have built-in assertions, we just need
|
|
// to call these functions to test them.
|
|
//
|
|
// We don't actually check that the metrics are correct here, e.g. that
|
|
// GetMinWidth(10) is a lower bound on the width of cells at level 10.
|
|
// It is easier to check these properties in s2cell_unittest, since
|
|
// S2Cell has methods to compute the cell vertices, etc.
|
|
|
|
for (int level = -2; level <= S2CellId.MAX_LEVEL + 3; ++level) {
|
|
double dWidth = (2 * S2Projections.MIN_WIDTH.deriv()) * Math.pow(2, -level);
|
|
if (level >= S2CellId.MAX_LEVEL + 3) {
|
|
dWidth = 0;
|
|
}
|
|
|
|
// Check boundary cases (exactly equal to a threshold value).
|
|
int expectedLevel = Math.max(0, Math.min(S2CellId.MAX_LEVEL, level));
|
|
assertEquals(S2Projections.MIN_WIDTH.getMinLevel(dWidth), expectedLevel);
|
|
assertEquals(S2Projections.MIN_WIDTH.getMaxLevel(dWidth), expectedLevel);
|
|
assertEquals(S2Projections.MIN_WIDTH.getClosestLevel(dWidth), expectedLevel);
|
|
|
|
// Also check non-boundary cases.
|
|
assertEquals(S2Projections.MIN_WIDTH.getMinLevel(1.2 * dWidth), expectedLevel);
|
|
assertEquals(S2Projections.MIN_WIDTH.getMaxLevel(0.8 * dWidth), expectedLevel);
|
|
assertEquals(S2Projections.MIN_WIDTH.getClosestLevel(1.2 * dWidth), expectedLevel);
|
|
assertEquals(S2Projections.MIN_WIDTH.getClosestLevel(0.8 * dWidth), expectedLevel);
|
|
|
|
// Same thing for area1.
|
|
double area1 = (4 * S2Projections.MIN_AREA.deriv()) * Math.pow(4, -level);
|
|
if (level <= -3) {
|
|
area1 = 0;
|
|
}
|
|
assertEquals(S2Projections.MIN_AREA.getMinLevel(area1), expectedLevel);
|
|
assertEquals(S2Projections.MIN_AREA.getMaxLevel(area1), expectedLevel);
|
|
assertEquals(S2Projections.MIN_AREA.getClosestLevel(area1), expectedLevel);
|
|
assertEquals(S2Projections.MIN_AREA.getMinLevel(1.2 * area1), expectedLevel);
|
|
assertEquals(S2Projections.MIN_AREA.getMaxLevel(0.8 * area1), expectedLevel);
|
|
assertEquals(S2Projections.MIN_AREA.getClosestLevel(1.2 * area1), expectedLevel);
|
|
assertEquals(S2Projections.MIN_AREA.getClosestLevel(0.8 * area1), expectedLevel);
|
|
}
|
|
}
|
|
|
|
public void testExp() {
|
|
for (int i = 0; i < 10; ++i) {
|
|
assertEquals(i + 1, S2.exp(Math.pow(2, i)));
|
|
}
|
|
|
|
for (int i = 0; i < 10; ++i) {
|
|
assertEquals(i + 1, S2.exp(-Math.pow(2, i)));
|
|
}
|
|
|
|
assertEquals(0, S2.exp(0));
|
|
assertEquals(2, S2.exp(3));
|
|
assertEquals(3, S2.exp(5));
|
|
}
|
|
}
|