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 import com.google.common.base.Splitter; 19 import com.google.common.collect.ImmutableList; 20 import com.google.common.collect.Iterables; 21 import com.google.common.collect.Lists; 22 23 import junit.framework.TestCase; 24 25 import java.util.List; 26 import java.util.Random; 27 28 public strictfp class GeometryTestCase extends TestCase { 29 30 public Random rand; 31 32 @Override setUp()33 protected void setUp() { 34 rand = new Random(123456); 35 } 36 assertDoubleNear(double a, double b)37 public void assertDoubleNear(double a, double b) { 38 assertDoubleNear(a, b, 1e-9); 39 } 40 assertDoubleNear(double a, double b, double error)41 public void assertDoubleNear(double a, double b, double error) { 42 assertTrue(a + error > b); 43 assertTrue(a < b + error); 44 } 45 46 // maybe these should be put in a special testing util class 47 /** Return a random unit-length vector. */ 48 public S2Point randomPoint() { 49 return S2Point.normalize(new S2Point( 50 2 * rand.nextDouble() - 1, 51 2 * rand.nextDouble() - 1, 52 2 * rand.nextDouble() - 1)); 53 } 54 55 /** 56 * Return a right-handed coordinate frame (three orthonormal vectors). Returns 57 * an array of three points: x,y,z 58 */ 59 public ImmutableList<S2Point> getRandomFrame() { 60 S2Point p0 = randomPoint(); 61 S2Point p1 = S2Point.normalize(S2Point.crossProd(p0, randomPoint())); 62 S2Point p2 = S2Point.normalize(S2Point.crossProd(p0, p1)); 63 return ImmutableList.of(p0, p1, p2); 64 } 65 66 /** 67 * Return a random cell id at the given level or at a randomly chosen level. 68 * The distribution is uniform over the space of cell ids, but only 69 * approximately uniform over the surface of the sphere. 70 */ 71 public S2CellId getRandomCellId(int level) { 72 int face = random(S2CellId.NUM_FACES); 73 long pos = rand.nextLong() & ((1L << (2 * S2CellId.MAX_LEVEL)) - 1); 74 return S2CellId.fromFacePosLevel(face, pos, level); 75 } 76 77 public S2CellId getRandomCellId() { 78 return getRandomCellId(random(S2CellId.MAX_LEVEL + 1)); 79 } 80 81 int random(int n) { 82 if (n == 0) { 83 return 0; 84 } 85 return rand.nextInt(n); 86 } 87 88 89 // Pick "base" uniformly from range [0,maxLog] and then return 90 // "base" random bits. The effect is to pick a number in the range 91 // [0,2^maxLog-1] with bias towards smaller numbers. 92 int skewed(int maxLog) { 93 final int base = Math.abs(rand.nextInt()) % (maxLog + 1); 94 // if (!base) return 0; // if 0==base, we & with 0 below. 95 // 96 // this distribution differs slightly from ACMRandom's Skewed, 97 // since 0 occurs approximately 3 times more than 1 here, and 98 // ACMRandom's Skewed never outputs 0. 99 return rand.nextInt() & ((1 << base) - 1); 100 } 101 102 /** 103 * Checks that "covering" completely covers the given region. If "check_tight" 104 * is true, also checks that it does not contain any cells that do not 105 * intersect the given region. ("id" is only used internally.) 106 */ 107 void checkCovering(S2Region region, S2CellUnion covering, boolean checkTight, S2CellId id) { 108 if (!id.isValid()) { 109 for (int face = 0; face < 6; ++face) { 110 checkCovering(region, covering, checkTight, S2CellId.fromFacePosLevel(face, 0, 0)); 111 } 112 return; 113 } 114 115 if (!region.mayIntersect(new S2Cell(id))) { 116 // If region does not intersect id, then neither should the covering. 117 if (checkTight) { 118 assertTrue(!covering.intersects(id)); 119 } 120 121 } else if (!covering.contains(id)) { 122 // The region may intersect id, but we can't assert that the covering 123 // intersects id because we may discover that the region does not actually 124 // intersect upon further subdivision. (MayIntersect is not exact.) 125 assertTrue(!region.contains(new S2Cell(id))); 126 assertTrue(!id.isLeaf()); 127 S2CellId end = id.childEnd(); 128 for (S2CellId child = id.childBegin(); !child.equals(end); child = child.next()) { 129 checkCovering(region, covering, checkTight, child); 130 } 131 } 132 } 133 134 S2Cap getRandomCap(double minArea, double maxArea) { 135 double capArea = maxArea 136 * Math.pow(minArea / maxArea, rand.nextDouble()); 137 assertTrue(capArea >= minArea && capArea <= maxArea); 138 139 // The surface area of a cap is 2*Pi times its height. 140 return S2Cap.fromAxisArea(randomPoint(), capArea); 141 } 142 143 S2Point samplePoint(S2Cap cap) { 144 // We consider the cap axis to be the "z" axis. We choose two other axes to 145 // complete the coordinate frame. 146 147 S2Point z = cap.axis(); 148 S2Point x = z.ortho(); 149 S2Point y = S2Point.crossProd(z, x); 150 151 // The surface area of a spherical cap is directly proportional to its 152 // height. First we choose a random height, and then we choose a random 153 // point along the circle at that height. 154 155 double h = rand.nextDouble() * cap.height(); 156 double theta = 2 * S2.M_PI * rand.nextDouble(); 157 double r = Math.sqrt(h * (2 - h)); // Radius of circle. 158 159 // (cos(theta)*r*x + sin(theta)*r*y + (1-h)*z).Normalize() 160 return S2Point.normalize(S2Point.add( 161 S2Point.add(S2Point.mul(x, Math.cos(theta) * r), S2Point.mul(y, Math.sin(theta) * r)), 162 S2Point.mul(z, (1 - h)))); 163 } 164 165 static void parseVertices(String str, List<S2Point> vertices) { 166 if (str == null) { 167 return; 168 } 169 170 for (String token : Splitter.on(',').split(str)) { 171 int colon = token.indexOf(':'); 172 if (colon == -1) { 173 throw new IllegalArgumentException( 174 "Illegal string:" + token + ". Should look like '35:20'"); 175 } 176 double lat = Double.parseDouble(token.substring(0, colon)); 177 double lng = Double.parseDouble(token.substring(colon + 1)); 178 vertices.add(S2LatLng.fromDegrees(lat, lng).toPoint()); 179 } 180 } 181 182 static S2Point makePoint(String str) { 183 List<S2Point> vertices = Lists.newArrayList(); 184 parseVertices(str, vertices); 185 return Iterables.getOnlyElement(vertices); 186 } 187 188 static S2Loop makeLoop(String str) { 189 List<S2Point> vertices = Lists.newArrayList(); 190 parseVertices(str, vertices); 191 return new S2Loop(vertices); 192 } 193 194 static S2Polygon makePolygon(String str) { 195 List<S2Loop> loops = Lists.newArrayList(); 196 197 for (String token : Splitter.on(';').omitEmptyStrings().split(str)) { 198 S2Loop loop = makeLoop(token); 199 loop.normalize(); 200 loops.add(loop); 201 } 202 203 return new S2Polygon(loops); 204 } 205 206 static S2Polyline makePolyline(String str) { 207 List<S2Point> vertices = Lists.newArrayList(); 208 parseVertices(str, vertices); 209 return new S2Polyline(vertices); 210 } 211 } 212