1 /* 2 * Copyright 2005 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.google.common.geometry; 17 18 public strictfp class S2CapTest extends GeometryTestCase { 19 getLatLngPoint(double latDegrees, double lngDegrees)20 public S2Point getLatLngPoint(double latDegrees, double lngDegrees) { 21 return S2LatLng.fromDegrees(latDegrees, lngDegrees).toPoint(); 22 } 23 24 // About 9 times the double-precision roundoff relative error. 25 public static final double EPS = 1e-15; 26 testBasic()27 public void testBasic() { 28 // Test basic properties of empty and full caps. 29 S2Cap empty = S2Cap.empty(); 30 S2Cap full = S2Cap.full(); 31 assertTrue(empty.isValid()); 32 assertTrue(empty.isEmpty()); 33 assertTrue(empty.complement().isFull()); 34 assertTrue(full.isValid()); 35 assertTrue(full.isFull()); 36 assertTrue(full.complement().isEmpty()); 37 assertEquals(full.height(), 2.0); 38 assertDoubleNear(full.angle().degrees(), 180); 39 40 // Containment and intersection of empty and full caps. 41 assertTrue(empty.contains(empty)); 42 assertTrue(full.contains(empty)); 43 assertTrue(full.contains(full)); 44 assertTrue(!empty.interiorIntersects(empty)); 45 assertTrue(full.interiorIntersects(full)); 46 assertTrue(!full.interiorIntersects(empty)); 47 48 // Singleton cap containing the x-axis. 49 S2Cap xaxis = S2Cap.fromAxisHeight(new S2Point(1, 0, 0), 0); 50 assertTrue(xaxis.contains(new S2Point(1, 0, 0))); 51 assertTrue(!xaxis.contains(new S2Point(1, 1e-20, 0))); 52 assertEquals(xaxis.angle().radians(), 0.0); 53 54 // Singleton cap containing the y-axis. 55 S2Cap yaxis = S2Cap.fromAxisAngle(new S2Point(0, 1, 0), S1Angle.radians(0)); 56 assertTrue(!yaxis.contains(xaxis.axis())); 57 assertEquals(xaxis.height(), 0.0); 58 59 // Check that the complement of a singleton cap is the full cap. 60 S2Cap xcomp = xaxis.complement(); 61 assertTrue(xcomp.isValid()); 62 assertTrue(xcomp.isFull()); 63 assertTrue(xcomp.contains(xaxis.axis())); 64 65 // Check that the complement of the complement is *not* the original. 66 assertTrue(xcomp.complement().isValid()); 67 assertTrue(xcomp.complement().isEmpty()); 68 assertTrue(!xcomp.complement().contains(xaxis.axis())); 69 70 // Check that very small caps can be represented accurately. 71 // Here "kTinyRad" is small enough that unit vectors perturbed by this 72 // amount along a tangent do not need to be renormalized. 73 final double kTinyRad = 1e-10; 74 S2Cap tiny = 75 S2Cap.fromAxisAngle(S2Point.normalize(new S2Point(1, 2, 3)), S1Angle.radians(kTinyRad)); 76 S2Point tangent = S2Point.normalize(S2Point.crossProd(tiny.axis(), new S2Point(3, 2, 1))); 77 assertTrue(tiny.contains(S2Point.add(tiny.axis(), S2Point.mul(tangent, 0.99 * kTinyRad)))); 78 assertTrue(!tiny.contains(S2Point.add(tiny.axis(), S2Point.mul(tangent, 1.01 * kTinyRad)))); 79 80 // Basic tests on a hemispherical cap. 81 S2Cap hemi = S2Cap.fromAxisHeight(S2Point.normalize(new S2Point(1, 0, 1)), 1); 82 assertEquals(hemi.complement().axis(), S2Point.neg(hemi.axis())); 83 assertEquals(hemi.complement().height(), 1.0); 84 assertTrue(hemi.contains(new S2Point(1, 0, 0))); 85 assertTrue(!hemi.complement().contains(new S2Point(1, 0, 0))); 86 assertTrue(hemi.contains(S2Point.normalize(new S2Point(1, 0, -(1 - EPS))))); 87 assertTrue(!hemi.interiorContains(S2Point.normalize(new S2Point(1, 0, -(1 + EPS))))); 88 89 // A concave cap. 90 S2Cap concave = S2Cap.fromAxisAngle(getLatLngPoint(80, 10), S1Angle.degrees(150)); 91 assertTrue(concave.contains(getLatLngPoint(-70 * (1 - EPS), 10))); 92 assertTrue(!concave.contains(getLatLngPoint(-70 * (1 + EPS), 10))); 93 assertTrue(concave.contains(getLatLngPoint(-50 * (1 - EPS), -170))); 94 assertTrue(!concave.contains(getLatLngPoint(-50 * (1 + EPS), -170))); 95 96 // Cap containment tests. 97 assertTrue(!empty.contains(xaxis)); 98 assertTrue(!empty.interiorIntersects(xaxis)); 99 assertTrue(full.contains(xaxis)); 100 assertTrue(full.interiorIntersects(xaxis)); 101 assertTrue(!xaxis.contains(full)); 102 assertTrue(!xaxis.interiorIntersects(full)); 103 assertTrue(xaxis.contains(xaxis)); 104 assertTrue(!xaxis.interiorIntersects(xaxis)); 105 assertTrue(xaxis.contains(empty)); 106 assertTrue(!xaxis.interiorIntersects(empty)); 107 assertTrue(hemi.contains(tiny)); 108 assertTrue(hemi.contains( 109 S2Cap.fromAxisAngle(new S2Point(1, 0, 0), S1Angle.radians(S2.M_PI_4 - EPS)))); 110 assertTrue(!hemi.contains( 111 S2Cap.fromAxisAngle(new S2Point(1, 0, 0), S1Angle.radians(S2.M_PI_4 + EPS)))); 112 assertTrue(concave.contains(hemi)); 113 assertTrue(concave.interiorIntersects(hemi.complement())); 114 assertTrue(!concave.contains(S2Cap.fromAxisHeight(S2Point.neg(concave.axis()), 0.1))); 115 } 116 testRectBound()117 public void testRectBound() { 118 // Empty and full caps. 119 assertTrue(S2Cap.empty().getRectBound().isEmpty()); 120 assertTrue(S2Cap.full().getRectBound().isFull()); 121 122 final double kDegreeEps = 1e-13; 123 // Maximum allowable error for latitudes and longitudes measured in 124 // degrees. (assertDoubleNear uses a fixed tolerance that is too small.) 125 126 // Cap that includes the south pole. 127 S2LatLngRect rect = 128 S2Cap.fromAxisAngle(getLatLngPoint(-45, 57), S1Angle.degrees(50)).getRectBound(); 129 assertDoubleNear(rect.latLo().degrees(), -90, kDegreeEps); 130 assertDoubleNear(rect.latHi().degrees(), 5, kDegreeEps); 131 assertTrue(rect.lng().isFull()); 132 133 // Cap that is tangent to the north pole. 134 rect = S2Cap.fromAxisAngle(S2Point.normalize(new S2Point(1, 0, 1)), S1Angle.radians(S2.M_PI_4)) 135 .getRectBound(); 136 assertDoubleNear(rect.lat().lo(), 0); 137 assertDoubleNear(rect.lat().hi(), S2.M_PI_2); 138 assertTrue(rect.lng().isFull()); 139 140 rect = S2Cap 141 .fromAxisAngle(S2Point.normalize(new S2Point(1, 0, 1)), S1Angle.degrees(45)).getRectBound(); 142 assertDoubleNear(rect.latLo().degrees(), 0, kDegreeEps); 143 assertDoubleNear(rect.latHi().degrees(), 90, kDegreeEps); 144 assertTrue(rect.lng().isFull()); 145 146 // The eastern hemisphere. 147 rect = S2Cap 148 .fromAxisAngle(new S2Point(0, 1, 0), S1Angle.radians(S2.M_PI_2 + 5e-16)).getRectBound(); 149 assertDoubleNear(rect.latLo().degrees(), -90, kDegreeEps); 150 assertDoubleNear(rect.latHi().degrees(), 90, kDegreeEps); 151 assertTrue(rect.lng().isFull()); 152 153 // A cap centered on the equator. 154 rect = S2Cap.fromAxisAngle(getLatLngPoint(0, 50), S1Angle.degrees(20)).getRectBound(); 155 assertDoubleNear(rect.latLo().degrees(), -20, kDegreeEps); 156 assertDoubleNear(rect.latHi().degrees(), 20, kDegreeEps); 157 assertDoubleNear(rect.lngLo().degrees(), 30, kDegreeEps); 158 assertDoubleNear(rect.lngHi().degrees(), 70, kDegreeEps); 159 160 // A cap centered on the north pole. 161 rect = S2Cap.fromAxisAngle(getLatLngPoint(90, 123), S1Angle.degrees(10)).getRectBound(); 162 assertDoubleNear(rect.latLo().degrees(), 80, kDegreeEps); 163 assertDoubleNear(rect.latHi().degrees(), 90, kDegreeEps); 164 assertTrue(rect.lng().isFull()); 165 } 166 testCells()167 public void testCells() { 168 // For each cube face, we construct some cells on 169 // that face and some caps whose positions are relative to that face, 170 // and then check for the expected intersection/containment results. 171 172 // The distance from the center of a face to one of its vertices. 173 final double kFaceRadius = Math.atan(S2.M_SQRT2); 174 175 for (int face = 0; face < 6; ++face) { 176 // The cell consisting of the entire face. 177 S2Cell rootCell = S2Cell.fromFacePosLevel(face, (byte) 0, 0); 178 179 // A leaf cell at the midpoint of the v=1 edge. 180 S2Cell edgeCell = new S2Cell(S2Projections.faceUvToXyz(face, 0, 1 - EPS)); 181 182 // A leaf cell at the u=1, v=1 corner. 183 S2Cell cornerCell = new S2Cell(S2Projections.faceUvToXyz(face, 1 - EPS, 1 - EPS)); 184 185 // Quick check for full and empty caps. 186 assertTrue(S2Cap.full().contains(rootCell)); 187 assertTrue(!S2Cap.empty().mayIntersect(rootCell)); 188 189 // Check intersections with the bounding caps of the leaf cells that are 190 // adjacent to 'corner_cell' along the Hilbert curve. Because this corner 191 // is at (u=1,v=1), the curve stays locally within the same cube face. 192 S2CellId first = cornerCell.id().prev().prev().prev(); 193 S2CellId last = cornerCell.id().next().next().next().next(); 194 for (S2CellId id = first; id.lessThan(last); id = id.next()) { 195 S2Cell cell = new S2Cell(id); 196 assertEquals(cell.getCapBound().contains(cornerCell), id.equals(cornerCell.id())); 197 assertEquals( 198 cell.getCapBound().mayIntersect(cornerCell), id.parent().contains(cornerCell.id())); 199 } 200 201 int antiFace = (face + 3) % 6; // Opposite face. 202 for (int capFace = 0; capFace < 6; ++capFace) { 203 // A cap that barely contains all of 'cap_face'. 204 S2Point center = S2Projections.getNorm(capFace); 205 S2Cap covering = S2Cap.fromAxisAngle(center, S1Angle.radians(kFaceRadius + EPS)); 206 assertEquals(covering.contains(rootCell), capFace == face); 207 assertEquals(covering.mayIntersect(rootCell), capFace != antiFace); 208 assertEquals(covering.contains(edgeCell), center.dotProd(edgeCell.getCenter()) > 0.1); 209 assertEquals(covering.contains(edgeCell), covering.mayIntersect(edgeCell)); 210 assertEquals(covering.contains(cornerCell), capFace == face); 211 assertEquals( 212 covering.mayIntersect(cornerCell), center.dotProd(cornerCell.getCenter()) > 0); 213 214 // A cap that barely intersects the edges of 'cap_face'. 215 S2Cap bulging = S2Cap.fromAxisAngle(center, S1Angle.radians(S2.M_PI_4 + EPS)); 216 assertTrue(!bulging.contains(rootCell)); 217 assertEquals(bulging.mayIntersect(rootCell), capFace != antiFace); 218 assertEquals(bulging.contains(edgeCell), capFace == face); 219 assertEquals(bulging.mayIntersect(edgeCell), center.dotProd(edgeCell.getCenter()) > 0.1); 220 assertTrue(!bulging.contains(cornerCell)); 221 assertTrue(!bulging.mayIntersect(cornerCell)); 222 223 // A singleton cap. 224 S2Cap singleton = S2Cap.fromAxisAngle(center, S1Angle.radians(0)); 225 assertEquals(singleton.mayIntersect(rootCell), capFace == face); 226 assertTrue(!singleton.mayIntersect(edgeCell)); 227 assertTrue(!singleton.mayIntersect(cornerCell)); 228 } 229 } 230 } 231 } 232