| /* |
| * 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 com.google.common.collect.Lists; |
| |
| import java.util.ArrayList; |
| import java.util.HashSet; |
| import java.util.List; |
| import java.util.Set; |
| import java.util.logging.Logger; |
| |
| public strictfp class S2CellUnionTest extends GeometryTestCase { |
| public static Logger logger = Logger.getLogger(S2CellUnionTest.class.getName()); |
| |
| public void testBasic() { |
| logger.info("TestBasic"); |
| |
| S2CellUnion empty = new S2CellUnion(); |
| ArrayList<S2CellId> ids = Lists.newArrayList(); |
| empty.initFromCellIds(ids); |
| assertEquals(0, empty.size()); |
| |
| S2CellId face1Id = S2CellId.fromFacePosLevel(1, 0, 0); |
| S2CellUnion face1Union = new S2CellUnion(); |
| ids.add(face1Id); |
| face1Union.initFromCellIds(ids); |
| assertEquals(1, face1Union.size()); |
| assertEquals(face1Id, face1Union.cellId(0)); |
| |
| S2CellId face2Id = S2CellId.fromFacePosLevel(2, 0, 0); |
| S2CellUnion face2Union = new S2CellUnion(); |
| ArrayList<Long> cellids = Lists.newArrayList(); |
| cellids.add(face2Id.id()); |
| face2Union.initFromIds(cellids); |
| assertEquals(1, face2Union.size()); |
| assertEquals(face2Id, face2Union.cellId(0)); |
| |
| S2Cell face1Cell = new S2Cell(face1Id); |
| S2Cell face2Cell = new S2Cell(face2Id); |
| assertTrue(face1Union.contains(face1Cell)); |
| assertTrue(!face1Union.contains(face2Cell)); |
| } |
| |
| public void testContainsCellUnion() { |
| logger.info("TestContainsCellUnion"); |
| |
| Set<S2CellId> randomCells = new HashSet<S2CellId>(); |
| for (int i = 0; i < 100; i++) { |
| randomCells.add(getRandomCellId(S2CellId.MAX_LEVEL)); |
| } |
| |
| S2CellUnion union = new S2CellUnion(); |
| union.initFromCellIds(Lists.newArrayList(randomCells)); |
| |
| // Add one more |
| while (!randomCells.add(getRandomCellId(S2CellId.MAX_LEVEL))) { |
| } |
| |
| S2CellUnion unionPlusOne = new S2CellUnion(); |
| unionPlusOne.initFromCellIds(Lists.newArrayList(randomCells)); |
| |
| assertTrue(unionPlusOne.contains(union)); |
| assertFalse(union.contains(unionPlusOne)); |
| |
| // Build the set of parent cells and check containment |
| Set<S2CellId> parents = new HashSet<S2CellId>(); |
| for (S2CellId cellId : union) { |
| parents.add(cellId.parent()); |
| } |
| |
| S2CellUnion parentUnion = new S2CellUnion(); |
| parentUnion.initFromCellIds(Lists.newArrayList(parents)); |
| |
| assertTrue(parentUnion.contains(union)); |
| assertFalse(union.contains(parentUnion)); |
| } |
| |
| private void addCells(S2CellId id, boolean selected, List<S2CellId> input, |
| ArrayList<S2CellId> expected) { |
| // Decides whether to add "id" and/or some of its descendants to the |
| // test case. If "selected" is true, then the region covered by "id" |
| // *must* be added to the test case (either by adding "id" itself, or |
| // some combination of its descendants, or both). If cell ids are to |
| // the test case "input", then the corresponding expected result after |
| // simplification is added to "expected". |
| |
| if (id.equals(S2CellId.none())) { |
| // Initial call: decide whether to add cell(s) from each face. |
| for (int face = 0; face < 6; ++face) { |
| addCells(S2CellId.fromFacePosLevel(face, 0, 0), false, input, expected); |
| } |
| return; |
| } |
| if (id.isLeaf()) { |
| // The rnd.OneIn() call below ensures that the parent of a leaf cell |
| // will always be selected (if we make it that far down the hierarchy). |
| assertTrue(selected); |
| input.add(id); |
| return; |
| } |
| // The following code ensures that the probability of selecting a cell |
| // at each level is approximately the same, i.e. we test normalization |
| // of cells at all levels. |
| if (!selected && random(S2CellId.MAX_LEVEL - id.level()) != 0) { |
| // Once a cell has been selected, the expected output is predetermined. |
| // We then make sure that cells are selected that will normalize to |
| // the desired output. |
| expected.add(id); |
| selected = true; |
| } |
| |
| // With the rnd.OneIn() constants below, this function adds an average |
| // of 5/6 * (kMaxLevel - level) cells to "input" where "level" is the |
| // level at which the cell was first selected (level 15 on average). |
| // Therefore the average number of input cells in a test case is about |
| // (5/6 * 15 * 6) = 75. The average number of output cells is about 6. |
| |
| // If a cell is selected, we add it to "input" with probability 5/6. |
| boolean added = false; |
| if (selected && random(6) != 0) { |
| input.add(id); |
| added = true; |
| } |
| int numChildren = 0; |
| S2CellId child = id.childBegin(); |
| for (int pos = 0; pos < 4; ++pos, child = child.next()) { |
| // If the cell is selected, on average we recurse on 4/12 = 1/3 child. |
| // This intentionally may result in a cell and some of its children |
| // being included in the test case. |
| // |
| // If the cell is not selected, on average we recurse on one child. |
| // We also make sure that we do not recurse on all 4 children, since |
| // then we might include all 4 children in the input case by accident |
| // (in which case the expected output would not be correct). |
| if (random(selected ? 12 : 4) == 0 && numChildren < 3) { |
| addCells(child, selected, input, expected); |
| ++numChildren; |
| } |
| // If this cell was selected but the cell itself was not added, we |
| // must ensure that all 4 children (or some combination of their |
| // descendents) are added. |
| if (selected && !added) { |
| addCells(child, selected, input, expected); |
| } |
| } |
| } |
| |
| public void testNormalize() { |
| logger.info("TestNormalize"); |
| |
| // Try a bunch of random test cases, and keep track of average |
| // statistics for normalization (to see if they agree with the |
| // analysis above). |
| S2CellUnion cellunion = new S2CellUnion(); |
| double inSum = 0, outSum = 0; |
| final int kIters = 2000; |
| for (int i = 0; i < kIters; ++i) { |
| ArrayList<S2CellId> input = Lists.newArrayList(); |
| ArrayList<S2CellId> expected = Lists.newArrayList(); |
| addCells(S2CellId.none(), false, input, expected); |
| inSum += input.size(); |
| outSum += expected.size(); |
| cellunion.initFromCellIds(input); |
| assertEquals(cellunion.size(), expected.size()); |
| |
| assertEquals(expected, cellunion.cellIds()); |
| |
| // Test GetCapBound(). |
| S2Cap cap = cellunion.getCapBound(); |
| for (int k = 0; k < cellunion.size(); ++k) { |
| assertTrue(cap.contains(new S2Cell(cellunion.cellId(k)))); |
| } |
| |
| // Test Contains(S2CellId) and Intersects(S2CellId). |
| for (int j = 0; j < input.size(); ++j) { |
| assertTrue(cellunion.contains(input.get(j))); |
| assertTrue(cellunion.intersects(input.get(j))); |
| if (!input.get(j).isFace()) { |
| assertTrue(cellunion.intersects(input.get(j).parent())); |
| if (input.get(j).level() > 1) { |
| assertTrue(cellunion.intersects(input.get(j).parent().parent())); |
| assertTrue(cellunion.intersects(input.get(j).parent(0))); |
| } |
| } |
| if (!input.get(j).isLeaf()) { |
| assertTrue(cellunion.contains(input.get(j).childBegin())); |
| assertTrue(cellunion.intersects(input.get(j).childBegin())); |
| assertTrue(cellunion.contains(input.get(j).childEnd().prev())); |
| assertTrue(cellunion.intersects(input.get(j).childEnd().prev())); |
| assertTrue(cellunion.contains(input.get(j).childBegin(S2CellId.MAX_LEVEL))); |
| assertTrue(cellunion.intersects(input.get(j).childBegin(S2CellId.MAX_LEVEL))); |
| } |
| } |
| for (int j = 0; j < expected.size(); ++j) { |
| if (!expected.get(j).isFace()) { |
| assertTrue(!cellunion.contains(expected.get(j).parent())); |
| assertTrue(!cellunion.contains(expected.get(j).parent(0))); |
| } |
| } |
| |
| // Test contains(S2CellUnion) and intersects(S2CellUnion) |
| ArrayList<S2CellId> x = Lists.newArrayList(); |
| ArrayList<S2CellId> y = Lists.newArrayList(); |
| ArrayList<S2CellId> xOrY = Lists.newArrayList(); |
| ArrayList<S2CellId> xAndY = Lists.newArrayList(); |
| for (int j = 0; j < input.size(); ++j) { |
| boolean inX = random(2) == 0; |
| boolean inY = random(2) == 0; |
| if (inX) { |
| x.add(input.get(j)); |
| } |
| if (inY) { |
| y.add(input.get(j)); |
| } |
| if (inX || inY) { |
| xOrY.add(input.get(j)); |
| } |
| } |
| S2CellUnion xCells = new S2CellUnion(); |
| S2CellUnion yCells = new S2CellUnion(); |
| S2CellUnion xOrYExpected = new S2CellUnion(); |
| S2CellUnion xAndYExpected = new S2CellUnion(); |
| xCells.initFromCellIds(x); |
| yCells.initFromCellIds(y); |
| xOrYExpected.initFromCellIds(xOrY); |
| |
| S2CellUnion xOrYCells = new S2CellUnion(); |
| xOrYCells.getUnion(xCells, yCells); |
| assertEquals(xOrYExpected, xOrYCells); |
| |
| // Compute the intersection of "x" with each cell of "y", |
| // check that this intersection is correct, and append the |
| // results to xAndYExpected. |
| for (int j = 0; j < yCells.size(); ++j) { |
| S2CellId yId = yCells.cellId(j); |
| S2CellUnion u = new S2CellUnion(); |
| u.getIntersection(xCells, yId); |
| for (int k = 0; k < xCells.size(); ++k) { |
| S2CellId xId = xCells.cellId(k); |
| if (xId.contains(yId)) { |
| assertEquals(1, u.size()); |
| assertEquals(yId, u.cellId(0)); |
| } else if (yId.contains(xId)) { |
| if (!u.contains(xId)) { |
| u.getIntersection(xCells, yId); |
| } |
| assertTrue(u.contains(xId)); |
| } |
| } |
| for (int k = 0; k < u.size(); ++k) { |
| assertTrue(xCells.contains(u.cellId(k))); |
| assertTrue(yId.contains(u.cellId(k))); |
| } |
| xAndY.addAll(u.cellIds()); |
| } |
| xAndYExpected.initFromCellIds(xAndY); |
| |
| S2CellUnion xAndYCells = new S2CellUnion(); |
| xAndYCells.getIntersection(xCells, yCells); |
| assertEquals(xAndYExpected, xAndYCells); |
| |
| ArrayList<S2CellId> test = Lists.newArrayList(); |
| ArrayList<S2CellId> dummy = Lists.newArrayList(); |
| |
| addCells(S2CellId.none(), false, test, dummy); |
| for (int j = 0; j < test.size(); ++j) { |
| boolean contains = false, intersects = false; |
| for (int k = 0; k < expected.size(); ++k) { |
| if (expected.get(k).contains(test.get(j))) { |
| contains = true; |
| } |
| if (expected.get(k).intersects(test.get(j))) { |
| intersects = true; |
| } |
| } |
| assertEquals(cellunion.contains(test.get(j)), contains); |
| assertEquals(cellunion.intersects(test.get(j)), intersects); |
| } |
| |
| } |
| } |
| |
| double getMaxAngle(S2CellUnion covering, S2Point axis) { |
| double maxAngle = 0; |
| for (int i = 0; i < covering.size(); ++i) { |
| S2Cell cell = new S2Cell(covering.cellId(i)); |
| S2Cap cellCap = cell.getCapBound(); |
| double angle = axis.angle(cellCap.axis()) + cellCap.angle().radians(); |
| maxAngle = Math.max(maxAngle, angle); |
| } |
| return maxAngle; |
| } |
| |
| public void testExpand() { |
| logger.info("TestExpand"); |
| |
| // This test generates coverings for caps of random sizes, and expands |
| // the coverings by a random radius, and then make sure that the new |
| // covering covers the expanded cap. It also makes sure that the |
| // new covering is not too much larger than expected. |
| |
| S2RegionCoverer coverer = new S2RegionCoverer(); |
| for (int i = 0; i < 1000; ++i) { |
| S2Cap cap = getRandomCap(S2Cell.averageArea(S2CellId.MAX_LEVEL), 4 * S2.M_PI); |
| |
| // Expand the cap by a random factor whose log is uniformly distributed |
| // between 0 and log(1e2). |
| S2Cap expandedCap = |
| S2Cap.fromAxisHeight(cap.axis(), Math.min(2.0, Math.pow(1e2, rand.nextDouble()) |
| * cap.height())); |
| |
| double radius = expandedCap.angle().radians() - cap.angle().radians(); |
| int maxLevelDiff = random(8); |
| |
| S2CellUnion covering = new S2CellUnion(); |
| coverer.setMaxCells(1 + skewed(10)); |
| coverer.getCovering(cap, covering); |
| checkCovering(cap, covering, true, new S2CellId()); |
| |
| double maxAngle = getMaxAngle(covering, cap.axis()); |
| int minLevel = S2CellId.MAX_LEVEL; |
| for (int j = 0; j < covering.size(); ++j) { |
| minLevel = Math.min(minLevel, covering.cellId(j).level()); |
| } |
| covering.expand(S1Angle.radians(radius), maxLevelDiff); |
| checkCovering(expandedCap, covering, false, new S2CellId()); |
| |
| int expandLevel = |
| Math.min(minLevel + maxLevelDiff, S2Projections.MIN_WIDTH.getMaxLevel(radius)); |
| double expandedMaxAngle = getMaxAngle(covering, cap.axis()); |
| |
| // If the covering includes a tiny cell along the boundary, in theory the |
| // maximum angle of the covering from the cap axis can increase by up to |
| // twice the maximum length of a cell diagonal. We allow for an increase |
| // of slightly more than this because cell bounding caps are not exact. |
| assertTrue(expandedMaxAngle - maxAngle <= 2.01 * S2Projections.MAX_DIAG |
| .getValue(expandLevel)); |
| } |
| } |
| |
| public void testLeafCellsCovered() { |
| S2CellUnion cellUnion = new S2CellUnion(); |
| |
| // empty union |
| assertEquals(0, cellUnion.leafCellsCovered()); |
| |
| ArrayList<S2CellId> ids = Lists.newArrayList(); |
| ids.add(S2CellId.fromFacePosLevel( |
| 0, (1L << ((S2CellId.MAX_LEVEL << 1) - 1)), S2CellId.MAX_LEVEL)); |
| |
| // One leaf on face 0. |
| cellUnion.initFromCellIds(ids); |
| assertEquals(1L, cellUnion.leafCellsCovered()); |
| |
| // Face 0. |
| ids.add(S2CellId.fromFacePosLevel(0, 0, 0)); |
| cellUnion.initFromCellIds(ids); |
| assertEquals(1L << 60, cellUnion.leafCellsCovered()); |
| |
| // Five faces. |
| cellUnion.expand(0); |
| assertEquals(5L << 60, cellUnion.leafCellsCovered()); |
| |
| // Whole world. |
| cellUnion.expand(0); |
| assertEquals(6L << 60, cellUnion.leafCellsCovered()); |
| |
| // Add some disjoint cells. |
| ids.add(S2CellId.fromFacePosLevel(1, 0, 1)); |
| ids.add(S2CellId.fromFacePosLevel(2, 0, 2)); |
| ids.add(S2CellId.fromFacePosLevel(2, (1L << 60), 2)); |
| ids.add(S2CellId.fromFacePosLevel(3, 0, 14)); |
| ids.add(S2CellId.fromFacePosLevel(4, (1L << 60), 15)); |
| ids.add(S2CellId.fromFacePosLevel(4, 0, 27)); |
| ids.add(S2CellId.fromFacePosLevel(5, 0, 30)); |
| cellUnion.initFromCellIds(ids); |
| long expected = 1L + (1L << 6) + (1L << 30) + (1L << 32) + (2L << 56) + (1L << 58) + (1L << 60); |
| assertEquals(expected, cellUnion.leafCellsCovered()); |
| } |
| |
| |
| public void testAverageBasedArea() { |
| S2CellUnion cellUnion = new S2CellUnion(); |
| |
| // empty union |
| assertEquals(0.0, cellUnion.averageBasedArea()); |
| |
| ArrayList<S2CellId> ids = Lists.newArrayList(); |
| ids.add(S2CellId.fromFacePosLevel(1, 0, 1)); |
| ids.add(S2CellId.fromFacePosLevel(5, 0, 30)); |
| cellUnion.initFromCellIds(ids); |
| |
| double expected = S2Cell.averageArea(S2CellId.MAX_LEVEL) * (1L + (1L << 58)); |
| assertEquals(expected, cellUnion.averageBasedArea()); |
| } |
| |
| public void testApproxArea() { |
| S2CellUnion cellUnion = new S2CellUnion(); |
| |
| // empty union |
| assertEquals(0.0, cellUnion.approxArea()); |
| |
| ArrayList<S2CellId> ids = Lists.newArrayList(); |
| ids.add(S2CellId.fromFacePosLevel(1, 0, 1)); |
| ids.add(S2CellId.fromFacePosLevel(5, 0, 30)); |
| cellUnion.initFromCellIds(ids); |
| |
| double expected = new S2Cell(ids.get(0)).approxArea() + new S2Cell(ids.get(1)).approxArea(); |
| assertEquals(expected, cellUnion.approxArea()); |
| } |
| |
| public void testExactArea() { |
| S2CellUnion cellUnion = new S2CellUnion(); |
| |
| // empty union |
| assertEquals(0.0, cellUnion.exactArea()); |
| |
| ArrayList<S2CellId> ids = Lists.newArrayList(); |
| ids.add(S2CellId.fromFacePosLevel(1, 0, 1)); |
| ids.add(S2CellId.fromFacePosLevel(5, 0, 30)); |
| cellUnion.initFromCellIds(ids); |
| |
| double expected = new S2Cell(ids.get(0)).exactArea() + new S2Cell(ids.get(1)).exactArea(); |
| assertEquals(expected, cellUnion.averageBasedArea()); |
| } |
| } |
