tests/com/google/common/geometry/S2Test.java - platform/external/s2-geometry-library-java - Git at Google

 /*
  * 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));
   }
 }
	/*
	* 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));
	}
	}