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 java.util.ArrayList; 19 import java.util.HashMap; 20 import java.util.logging.Logger; 21 22 public strictfp class S2RegionCovererTest extends GeometryTestCase { 23 private static Logger logger = Logger.getLogger(S2RegionCovererTest.class.getName()); 24 testRandomCells()25 public void testRandomCells() { 26 logger.info("TestRandomCells"); 27 28 S2RegionCoverer coverer = new S2RegionCoverer(); 29 coverer.setMaxCells(1); 30 31 // Test random cell ids at all levels. 32 for (int i = 0; i < 10000; ++i) { 33 S2CellId id = getRandomCellId(); 34 S2CellUnion covering = new S2CellUnion(); 35 coverer.getCovering(new S2Cell(id), covering.cellIds()); 36 assertEquals(covering.size(), 1); 37 assertEquals(covering.cellId(0), id); 38 } 39 } 40 checkCovering( S2RegionCoverer coverer, S2Region region, ArrayList<S2CellId> covering, boolean interior)41 public void checkCovering( 42 S2RegionCoverer coverer, S2Region region, ArrayList<S2CellId> covering, boolean interior) { 43 44 // Keep track of how many cells have the same coverer.min_level() ancestor. 45 HashMap<S2CellId, Integer> minLevelCells = new HashMap<S2CellId, Integer>(); 46 for (int i = 0; i < covering.size(); ++i) { 47 int level = covering.get(i).level(); 48 assertTrue(level >= coverer.minLevel()); 49 assertTrue(level <= coverer.maxLevel()); 50 assertEquals((level - coverer.minLevel()) % coverer.levelMod(), 0); 51 S2CellId key = covering.get(i).parent(coverer.minLevel()); 52 if (!minLevelCells.containsKey(key)) { 53 minLevelCells.put(key, 1); 54 } else { 55 minLevelCells.put(key, minLevelCells.get(key) + 1); 56 } 57 } 58 if (covering.size() > coverer.maxCells()) { 59 // If the covering has more than the requested number of cells, then check 60 // that the cell count cannot be reduced by using the parent of some cell. 61 for (Integer i : minLevelCells.values()) { 62 assertEquals(i.intValue(), 1); 63 } 64 } 65 66 if (interior) { 67 for (int i = 0; i < covering.size(); ++i) { 68 assertTrue(region.contains(new S2Cell(covering.get(i)))); 69 } 70 } else { 71 S2CellUnion cellUnion = new S2CellUnion(); 72 cellUnion.initFromCellIds(covering); 73 checkCovering(region, cellUnion, true, new S2CellId()); 74 } 75 } 76 testRandomCaps()77 public void testRandomCaps() { 78 logger.info("TestRandomCaps"); 79 80 final int kMaxLevel = S2CellId.MAX_LEVEL; 81 S2RegionCoverer coverer = new S2RegionCoverer(); 82 for (int i = 0; i < 1000; ++i) { 83 do { 84 coverer.setMinLevel(random(kMaxLevel + 1)); 85 coverer.setMaxLevel(random(kMaxLevel + 1)); 86 } while (coverer.minLevel() > coverer.maxLevel()); 87 coverer.setMaxCells(skewed(10)); 88 coverer.setLevelMod(1 + random(3)); 89 double maxArea = Math.min( 90 4 * S2.M_PI, (3 * coverer.maxCells() + 1) * S2Cell.averageArea(coverer.minLevel())); 91 S2Cap cap = getRandomCap(0.1 * S2Cell.averageArea(kMaxLevel), maxArea); 92 ArrayList<S2CellId> covering = new ArrayList<S2CellId>(); 93 ArrayList<S2CellId> interior = new ArrayList<S2CellId>(); 94 95 coverer.getCovering(cap, covering); 96 checkCovering(coverer, cap, covering, false); 97 98 coverer.getInteriorCovering(cap, interior); 99 checkCovering(coverer, cap, interior, true); 100 101 102 // Check that GetCovering is deterministic. 103 ArrayList<S2CellId> covering2 = new ArrayList<S2CellId>(); 104 coverer.getCovering(cap, covering2); 105 assertTrue(covering.equals(covering2)); 106 107 // Also check S2CellUnion.denormalize(). The denormalized covering 108 // may still be different and smaller than "covering" because 109 // S2RegionCoverer does not guarantee that it will not output all four 110 // children of the same parent. 111 S2CellUnion cells = new S2CellUnion(); 112 cells.initFromCellIds(covering); 113 ArrayList<S2CellId> denormalized = new ArrayList<S2CellId>(); 114 cells.denormalize(coverer.minLevel(), coverer.levelMod(), denormalized); 115 checkCovering(coverer, cap, denormalized, false); 116 } 117 } 118 testSimpleCoverings()119 public void testSimpleCoverings() { 120 logger.info("TestSimpleCoverings"); 121 122 final int kMaxLevel = S2CellId.MAX_LEVEL; 123 S2RegionCoverer coverer = new S2RegionCoverer(); 124 coverer.setMaxCells(Integer.MAX_VALUE); 125 for (int i = 0; i < 1000; ++i) { 126 int level = random(kMaxLevel + 1); 127 coverer.setMinLevel(level); 128 coverer.setMaxLevel(level); 129 double maxArea = Math.min(4 * S2.M_PI, 1000 * S2Cell.averageArea(level)); 130 S2Cap cap = getRandomCap(0.1 * S2Cell.averageArea(kMaxLevel), maxArea); 131 ArrayList<S2CellId> covering = new ArrayList<S2CellId>(); 132 S2RegionCoverer.getSimpleCovering(cap, cap.axis(), level, covering); 133 checkCovering(coverer, cap, covering, false); 134 } 135 } 136 } 137