1 // Copyright 2023 Google Inc. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 package s2 16 17 // ShapeIndexRegion wraps a ShapeIndex and implements the Region interface. 18 // This allows RegionCoverer to work with ShapeIndexes as well as being 19 // able to be used by some of the Query types. 20 type ShapeIndexRegion struct { 21 index *ShapeIndex 22 containsQuery *ContainsPointQuery 23 iter *ShapeIndexIterator 24 } 25 26 // TODO(roberts): Uncomment once implementation is complete. 27 // Enforce Region interface satisfaction similar to other types that implement Region. 28 // var _ Region = (*ShapeIndexRegion)(nil) 29 30 // CapBound returns a bounding spherical cap for this collection of geometry. 31 // This is not guaranteed to be exact. 32 func (s *ShapeIndexRegion) CapBound() Cap { 33 cu := CellUnion(s.CellUnionBound()) 34 return cu.CapBound() 35 } 36 37 // RectBound returns a bounding rectangle for this collection of geometry. 38 // The bounds are not guaranteed to be tight. 39 func (s *ShapeIndexRegion) RectBound() Rect { 40 cu := CellUnion(s.CellUnionBound()) 41 return cu.RectBound() 42 } 43 44 // CellUnionBound returns the bounding CellUnion for this collection of geometry. 45 // This method currently returns at most 4 cells, unless the index spans 46 // multiple faces in which case it may return up to 6 cells. 47 func (s *ShapeIndexRegion) CellUnionBound() []CellID { 48 // We find the range of Cells spanned by the index and choose a level such 49 // that the entire index can be covered with just a few cells. There are 50 // two cases: 51 // 52 // - If the index intersects two or more faces, then for each intersected 53 // face we add one cell to the covering. Rather than adding the entire 54 // face, instead we add the smallest Cell that covers the ShapeIndex 55 // cells within that face. 56 // 57 // - If the index intersects only one face, then we first find the smallest 58 // cell S that contains the index cells (just like the case above). 59 // However rather than using the cell S itself, instead we repeat this 60 // process for each of its child cells. In other words, for each 61 // child cell C we add the smallest Cell C' that covers the index cells 62 // within C. This extra step is relatively cheap and produces much 63 // tighter coverings when the ShapeIndex consists of a small region 64 // near the center of a large Cell. 65 var cellIDs []CellID 66 67 // Find the last CellID in the index. 68 s.iter.End() 69 if !s.iter.Prev() { 70 return cellIDs // Empty index. 71 } 72 lastIndexID := s.iter.CellID() 73 s.iter.Begin() 74 if s.iter.CellID() != lastIndexID { 75 // The index has at least two cells. Choose a CellID level such that 76 // the entire index can be spanned with at most 6 cells (if the index 77 // spans multiple faces) or 4 cells (it the index spans a single face). 78 level, ok := s.iter.CellID().CommonAncestorLevel(lastIndexID) 79 if !ok { 80 // C++ returns -1 for no common level, ours returns 0. Set 81 // to -1 so the next ++ puts us at the same place as C++ does. 82 level = -1 83 } 84 level++ 85 86 // For each cell C at the chosen level, we compute the smallest Cell 87 // that covers the ShapeIndex cells within C. 88 lastID := lastIndexID.Parent(level) 89 for id := s.iter.CellID().Parent(level); id != lastID; id = id.Next() { 90 // If the cell C does not contain any index cells, then skip it. 91 if id.RangeMax() < s.iter.CellID() { 92 continue 93 } 94 95 // Find the range of index cells contained by C and then shrink C so 96 // that it just covers those cells. 97 first := s.iter.CellID() 98 s.iter.seek(id.RangeMax().Next()) 99 s.iter.Prev() 100 cellIDs = s.coverRange(first, s.iter.CellID(), cellIDs) 101 s.iter.Next() 102 } 103 } 104 105 return s.coverRange(s.iter.CellID(), lastIndexID, cellIDs) 106 } 107 108 // coverRange computes the smallest CellID that covers the Cell range (first, last) 109 // and returns the updated slice. 110 // 111 // This requires first and last have a common ancestor. 112 func (s *ShapeIndexRegion) coverRange(first, last CellID, cellIDs []CellID) []CellID { 113 // The range consists of a single index cell. 114 if first == last { 115 return append(cellIDs, first) 116 } 117 118 // Add the lowest common ancestor of the given range. 119 level, ok := first.CommonAncestorLevel(last) 120 if !ok { 121 return append(cellIDs, CellID(0)) 122 } 123 return append(cellIDs, first.Parent(level)) 124 } 125 126 // TODO(roberts): remaining methods 127 /* 128 // ContainsCell(target Cell) bool { 129 // IntersectsCell(target Cell) bool { 130 // ContainsPoint(p Point) bool { 131 // contains(id CellID, clipped clippedShape, p Point) bool { 132 // anyEdgeIntersects(clipped clippedShape, target Cell) bool { 133 */ 134