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 
77   // b/280346791 - commented in Android as this test occasionally takes a long time, probably
78   // due to an upstream bug that generates pathological test geometry cases.
79   /*
80   public void testRandomCaps() {
81     logger.info("TestRandomCaps");
82 
83     final int kMaxLevel = S2CellId.MAX_LEVEL;
84     S2RegionCoverer coverer = new S2RegionCoverer();
85     for (int i = 0; i < 1000; ++i) {
86       do {
87         coverer.setMinLevel(random(kMaxLevel + 1));
88         coverer.setMaxLevel(random(kMaxLevel + 1));
89       } while (coverer.minLevel() > coverer.maxLevel());
90       coverer.setMaxCells(skewed(10));
91       coverer.setLevelMod(1 + random(3));
92       double maxArea = Math.min(
93           4 * S2.M_PI, (3 * coverer.maxCells() + 1) * S2Cell.averageArea(coverer.minLevel()));
94       S2Cap cap = getRandomCap(0.1 * S2Cell.averageArea(kMaxLevel), maxArea);
95       ArrayList<S2CellId> covering = new ArrayList<S2CellId>();
96       ArrayList<S2CellId> interior = new ArrayList<S2CellId>();
97 
98       coverer.getCovering(cap, covering);
99       checkCovering(coverer, cap, covering, false);
100 
101       coverer.getInteriorCovering(cap, interior);
102       checkCovering(coverer, cap, interior, true);
103 
104 
105       // Check that GetCovering is deterministic.
106       ArrayList<S2CellId> covering2 = new ArrayList<S2CellId>();
107       coverer.getCovering(cap, covering2);
108       assertTrue(covering.equals(covering2));
109 
110       // Also check S2CellUnion.denormalize(). The denormalized covering
111       // may still be different and smaller than "covering" because
112       // S2RegionCoverer does not guarantee that it will not output all four
113       // children of the same parent.
114       S2CellUnion cells = new S2CellUnion();
115       cells.initFromCellIds(covering);
116       ArrayList<S2CellId> denormalized = new ArrayList<S2CellId>();
117       cells.denormalize(coverer.minLevel(), coverer.levelMod(), denormalized);
118       checkCovering(coverer, cap, denormalized, false);
119     }
120   }
121   */
122 
testSimpleCoverings()123   public void testSimpleCoverings() {
124     logger.info("TestSimpleCoverings");
125 
126     final int kMaxLevel = S2CellId.MAX_LEVEL;
127     S2RegionCoverer coverer = new S2RegionCoverer();
128     coverer.setMaxCells(Integer.MAX_VALUE);
129     for (int i = 0; i < 1000; ++i) {
130       int level = random(kMaxLevel + 1);
131       coverer.setMinLevel(level);
132       coverer.setMaxLevel(level);
133       double maxArea = Math.min(4 * S2.M_PI, 1000 * S2Cell.averageArea(level));
134       S2Cap cap = getRandomCap(0.1 * S2Cell.averageArea(kMaxLevel), maxArea);
135       ArrayList<S2CellId> covering = new ArrayList<S2CellId>();
136       S2RegionCoverer.getSimpleCovering(cap, cap.axis(), level, covering);
137       checkCovering(coverer, cap, covering, false);
138     }
139   }
140 }
141