tests/com/google/common/geometry/S2CapTest.java

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

public strictfp class S2CapTest extends GeometryTestCase {

  public S2Point getLatLngPoint(double latDegrees, double lngDegrees) {
    return S2LatLng.fromDegrees(latDegrees, lngDegrees).toPoint();
  }

  // About 9 times the double-precision roundoff relative error.
  public static final double EPS = 1e-15;

  public void testBasic() {
    // Test basic properties of empty and full caps.
    S2Cap empty = S2Cap.empty();
    S2Cap full = S2Cap.full();
    assertTrue(empty.isValid());
    assertTrue(empty.isEmpty());
    assertTrue(empty.complement().isFull());
    assertTrue(full.isValid());
    assertTrue(full.isFull());
    assertTrue(full.complement().isEmpty());
    assertEquals(full.height(), 2.0);
    assertDoubleNear(full.angle().degrees(), 180);

    // Containment and intersection of empty and full caps.
    assertTrue(empty.contains(empty));
    assertTrue(full.contains(empty));
    assertTrue(full.contains(full));
    assertTrue(!empty.interiorIntersects(empty));
    assertTrue(full.interiorIntersects(full));
    assertTrue(!full.interiorIntersects(empty));

    // Singleton cap containing the x-axis.
    S2Cap xaxis = S2Cap.fromAxisHeight(new S2Point(1, 0, 0), 0);
    assertTrue(xaxis.contains(new S2Point(1, 0, 0)));
    assertTrue(!xaxis.contains(new S2Point(1, 1e-20, 0)));
    assertEquals(xaxis.angle().radians(), 0.0);

    // Singleton cap containing the y-axis.
    S2Cap yaxis = S2Cap.fromAxisAngle(new S2Point(0, 1, 0), S1Angle.radians(0));
    assertTrue(!yaxis.contains(xaxis.axis()));
    assertEquals(xaxis.height(), 0.0);

    // Check that the complement of a singleton cap is the full cap.
    S2Cap xcomp = xaxis.complement();
    assertTrue(xcomp.isValid());
    assertTrue(xcomp.isFull());
    assertTrue(xcomp.contains(xaxis.axis()));

    // Check that the complement of the complement is *not* the original.
    assertTrue(xcomp.complement().isValid());
    assertTrue(xcomp.complement().isEmpty());
    assertTrue(!xcomp.complement().contains(xaxis.axis()));

    // Check that very small caps can be represented accurately.
    // Here "kTinyRad" is small enough that unit vectors perturbed by this
    // amount along a tangent do not need to be renormalized.
    final double kTinyRad = 1e-10;
    S2Cap tiny =
        S2Cap.fromAxisAngle(S2Point.normalize(new S2Point(1, 2, 3)), S1Angle.radians(kTinyRad));
    S2Point tangent = S2Point.normalize(S2Point.crossProd(tiny.axis(), new S2Point(3, 2, 1)));
    assertTrue(tiny.contains(S2Point.add(tiny.axis(), S2Point.mul(tangent, 0.99 * kTinyRad))));
    assertTrue(!tiny.contains(S2Point.add(tiny.axis(), S2Point.mul(tangent, 1.01 * kTinyRad))));

    // Basic tests on a hemispherical cap.
    S2Cap hemi = S2Cap.fromAxisHeight(S2Point.normalize(new S2Point(1, 0, 1)), 1);
    assertEquals(hemi.complement().axis(), S2Point.neg(hemi.axis()));
    assertEquals(hemi.complement().height(), 1.0);
    assertTrue(hemi.contains(new S2Point(1, 0, 0)));
    assertTrue(!hemi.complement().contains(new S2Point(1, 0, 0)));
    assertTrue(hemi.contains(S2Point.normalize(new S2Point(1, 0, -(1 - EPS)))));
    assertTrue(!hemi.interiorContains(S2Point.normalize(new S2Point(1, 0, -(1 + EPS)))));

    // A concave cap.
    S2Cap concave = S2Cap.fromAxisAngle(getLatLngPoint(80, 10), S1Angle.degrees(150));
    assertTrue(concave.contains(getLatLngPoint(-70 * (1 - EPS), 10)));
    assertTrue(!concave.contains(getLatLngPoint(-70 * (1 + EPS), 10)));
    assertTrue(concave.contains(getLatLngPoint(-50 * (1 - EPS), -170)));
    assertTrue(!concave.contains(getLatLngPoint(-50 * (1 + EPS), -170)));

    // Cap containment tests.
    assertTrue(!empty.contains(xaxis));
    assertTrue(!empty.interiorIntersects(xaxis));
    assertTrue(full.contains(xaxis));
    assertTrue(full.interiorIntersects(xaxis));
    assertTrue(!xaxis.contains(full));
    assertTrue(!xaxis.interiorIntersects(full));
    assertTrue(xaxis.contains(xaxis));
    assertTrue(!xaxis.interiorIntersects(xaxis));
    assertTrue(xaxis.contains(empty));
    assertTrue(!xaxis.interiorIntersects(empty));
    assertTrue(hemi.contains(tiny));
    assertTrue(hemi.contains(
        S2Cap.fromAxisAngle(new S2Point(1, 0, 0), S1Angle.radians(S2.M_PI_4 - EPS))));
    assertTrue(!hemi.contains(
        S2Cap.fromAxisAngle(new S2Point(1, 0, 0), S1Angle.radians(S2.M_PI_4 + EPS))));
    assertTrue(concave.contains(hemi));
    assertTrue(concave.interiorIntersects(hemi.complement()));
    assertTrue(!concave.contains(S2Cap.fromAxisHeight(S2Point.neg(concave.axis()), 0.1)));
  }

  public void testRectBound() {
    // Empty and full caps.
    assertTrue(S2Cap.empty().getRectBound().isEmpty());
    assertTrue(S2Cap.full().getRectBound().isFull());

    final double kDegreeEps = 1e-13;
    // Maximum allowable error for latitudes and longitudes measured in
    // degrees. (assertDoubleNear uses a fixed tolerance that is too small.)

    // Cap that includes the south pole.
    S2LatLngRect rect =
        S2Cap.fromAxisAngle(getLatLngPoint(-45, 57), S1Angle.degrees(50)).getRectBound();
    assertDoubleNear(rect.latLo().degrees(), -90, kDegreeEps);
    assertDoubleNear(rect.latHi().degrees(), 5, kDegreeEps);
    assertTrue(rect.lng().isFull());

    // Cap that is tangent to the north pole.
    rect = S2Cap.fromAxisAngle(S2Point.normalize(new S2Point(1, 0, 1)), S1Angle.radians(S2.M_PI_4))
        .getRectBound();
    assertDoubleNear(rect.lat().lo(), 0);
    assertDoubleNear(rect.lat().hi(), S2.M_PI_2);
    assertTrue(rect.lng().isFull());

    rect = S2Cap
        .fromAxisAngle(S2Point.normalize(new S2Point(1, 0, 1)), S1Angle.degrees(45)).getRectBound();
    assertDoubleNear(rect.latLo().degrees(), 0, kDegreeEps);
    assertDoubleNear(rect.latHi().degrees(), 90, kDegreeEps);
    assertTrue(rect.lng().isFull());

    // The eastern hemisphere.
    rect = S2Cap
        .fromAxisAngle(new S2Point(0, 1, 0), S1Angle.radians(S2.M_PI_2 + 5e-16)).getRectBound();
    assertDoubleNear(rect.latLo().degrees(), -90, kDegreeEps);
    assertDoubleNear(rect.latHi().degrees(), 90, kDegreeEps);
    assertTrue(rect.lng().isFull());

    // A cap centered on the equator.
    rect = S2Cap.fromAxisAngle(getLatLngPoint(0, 50), S1Angle.degrees(20)).getRectBound();
    assertDoubleNear(rect.latLo().degrees(), -20, kDegreeEps);
    assertDoubleNear(rect.latHi().degrees(), 20, kDegreeEps);
    assertDoubleNear(rect.lngLo().degrees(), 30, kDegreeEps);
    assertDoubleNear(rect.lngHi().degrees(), 70, kDegreeEps);

    // A cap centered on the north pole.
    rect = S2Cap.fromAxisAngle(getLatLngPoint(90, 123), S1Angle.degrees(10)).getRectBound();
    assertDoubleNear(rect.latLo().degrees(), 80, kDegreeEps);
    assertDoubleNear(rect.latHi().degrees(), 90, kDegreeEps);
    assertTrue(rect.lng().isFull());
  }

  public void testCells() {
    // For each cube face, we construct some cells on
    // that face and some caps whose positions are relative to that face,
    // and then check for the expected intersection/containment results.

    // The distance from the center of a face to one of its vertices.
    final double kFaceRadius = Math.atan(S2.M_SQRT2);

    for (int face = 0; face < 6; ++face) {
      // The cell consisting of the entire face.
      S2Cell rootCell = S2Cell.fromFacePosLevel(face, (byte) 0, 0);

      // A leaf cell at the midpoint of the v=1 edge.
      S2Cell edgeCell = new S2Cell(S2Projections.faceUvToXyz(face, 0, 1 - EPS));

      // A leaf cell at the u=1, v=1 corner.
      S2Cell cornerCell = new S2Cell(S2Projections.faceUvToXyz(face, 1 - EPS, 1 - EPS));

      // Quick check for full and empty caps.
      assertTrue(S2Cap.full().contains(rootCell));
      assertTrue(!S2Cap.empty().mayIntersect(rootCell));

      // Check intersections with the bounding caps of the leaf cells that are
      // adjacent to 'corner_cell' along the Hilbert curve. Because this corner
      // is at (u=1,v=1), the curve stays locally within the same cube face.
      S2CellId first = cornerCell.id().prev().prev().prev();
      S2CellId last = cornerCell.id().next().next().next().next();
      for (S2CellId id = first; id.lessThan(last); id = id.next()) {
        S2Cell cell = new S2Cell(id);
        assertEquals(cell.getCapBound().contains(cornerCell), id.equals(cornerCell.id()));
        assertEquals(
            cell.getCapBound().mayIntersect(cornerCell), id.parent().contains(cornerCell.id()));
      }

      int antiFace = (face + 3) % 6; // Opposite face.
      for (int capFace = 0; capFace < 6; ++capFace) {
        // A cap that barely contains all of 'cap_face'.
        S2Point center = S2Projections.getNorm(capFace);
        S2Cap covering = S2Cap.fromAxisAngle(center, S1Angle.radians(kFaceRadius + EPS));
        assertEquals(covering.contains(rootCell), capFace == face);
        assertEquals(covering.mayIntersect(rootCell), capFace != antiFace);
        assertEquals(covering.contains(edgeCell), center.dotProd(edgeCell.getCenter()) > 0.1);
        assertEquals(covering.contains(edgeCell), covering.mayIntersect(edgeCell));
        assertEquals(covering.contains(cornerCell), capFace == face);
        assertEquals(
            covering.mayIntersect(cornerCell), center.dotProd(cornerCell.getCenter()) > 0);

        // A cap that barely intersects the edges of 'cap_face'.
        S2Cap bulging = S2Cap.fromAxisAngle(center, S1Angle.radians(S2.M_PI_4 + EPS));
        assertTrue(!bulging.contains(rootCell));
        assertEquals(bulging.mayIntersect(rootCell), capFace != antiFace);
        assertEquals(bulging.contains(edgeCell), capFace == face);
        assertEquals(bulging.mayIntersect(edgeCell), center.dotProd(edgeCell.getCenter()) > 0.1);
        assertTrue(!bulging.contains(cornerCell));
        assertTrue(!bulging.mayIntersect(cornerCell));

        // A singleton cap.
        S2Cap singleton = S2Cap.fromAxisAngle(center, S1Angle.radians(0));
        assertEquals(singleton.mayIntersect(rootCell), capFace == face);
        assertTrue(!singleton.mayIntersect(edgeCell));
        assertTrue(!singleton.mayIntersect(cornerCell));
      }
    }
  }
}