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 // Shape interface enforcement 18 var _ Shape = (*LaxPolygon)(nil) 19 20 // LaxPolygon represents a region defined by a collection of zero or more 21 // closed loops. The interior is the region to the left of all loops. This 22 // is similar to Polygon except that this class supports polygons 23 // with degeneracies. Degeneracies are of two types: degenerate edges (from a 24 // vertex to itself) and sibling edge pairs (consisting of two oppositely 25 // oriented edges). Degeneracies can represent either "shells" or "holes" 26 // depending on the loop they are contained by. For example, a degenerate 27 // edge or sibling pair contained by a "shell" would be interpreted as a 28 // degenerate hole. Such edges form part of the boundary of the polygon. 29 // 30 // Loops with fewer than three vertices are interpreted as follows: 31 // - A loop with two vertices defines two edges (in opposite directions). 32 // - A loop with one vertex defines a single degenerate edge. 33 // - A loop with no vertices is interpreted as the "full loop" containing 34 // 35 // all points on the sphere. If this loop is present, then all other loops 36 // must form degeneracies (i.e., degenerate edges or sibling pairs). For 37 // example, two loops {} and {X} would be interpreted as the full polygon 38 // with a degenerate single-point hole at X. 39 // 40 // LaxPolygon does not have any error checking, and it is perfectly fine to 41 // create LaxPolygon objects that do not meet the requirements below (e.g., in 42 // order to analyze or fix those problems). However, LaxPolygons must satisfy 43 // some additional conditions in order to perform certain operations: 44 // 45 // - In order to be valid for point containment tests, the polygon must 46 // 47 // satisfy the "interior is on the left" rule. This means that there must 48 // not be any crossing edges, and if there are duplicate edges then all but 49 // at most one of them must belong to a sibling pair (i.e., the number of 50 // edges in opposite directions must differ by at most one). 51 // 52 // - To be valid for polygon operations (BoundaryOperation), degenerate 53 // 54 // edges and sibling pairs cannot coincide with any other edges. For 55 // example, the following situations are not allowed: 56 // 57 // {AA, AA} // degenerate edge coincides with another edge 58 // {AA, AB} // degenerate edge coincides with another edge 59 // {AB, BA, AB} // sibling pair coincides with another edge 60 // 61 // Note that LaxPolygon is much faster to initialize and is more compact than 62 // Polygon, but unlike Polygon it does not have any built-in operations. 63 // Instead you should use ShapeIndex based operations such as BoundaryOperation, 64 // ClosestEdgeQuery, etc. 65 type LaxPolygon struct { 66 numLoops int 67 vertices []Point 68 69 numVerts int 70 cumulativeVertices []int 71 72 // TODO(roberts): C++ adds a prevLoop int field that claims to boost 73 // chain position lookups by 1.5-4.5x. Benchmark to see if this 74 // is useful here. 75 } 76 77 // LaxPolygonFromPolygon creates a LaxPolygon from the given Polygon. 78 func LaxPolygonFromPolygon(p *Polygon) *LaxPolygon { 79 spans := make([][]Point, len(p.loops)) 80 for i, loop := range p.loops { 81 if loop.IsFull() { 82 spans[i] = []Point{} // Empty span. 83 } else { 84 spans[i] = make([]Point, len(loop.vertices)) 85 copy(spans[i], loop.vertices) 86 } 87 } 88 return LaxPolygonFromPoints(spans) 89 } 90 91 // LaxPolygonFromPoints creates a LaxPolygon from the given points. 92 func LaxPolygonFromPoints(loops [][]Point) *LaxPolygon { 93 p := &LaxPolygon{} 94 p.numLoops = len(loops) 95 if p.numLoops == 0 { 96 p.numVerts = 0 97 p.vertices = nil 98 } else if p.numLoops == 1 { 99 p.numVerts = len(loops[0]) 100 p.vertices = make([]Point, p.numVerts) 101 copy(p.vertices, loops[0]) 102 } else { 103 p.cumulativeVertices = make([]int, p.numLoops+1) 104 numVertices := 0 105 for i, loop := range loops { 106 p.cumulativeVertices[i] = numVertices 107 numVertices += len(loop) 108 } 109 110 p.cumulativeVertices[p.numLoops] = numVertices 111 for _, points := range loops { 112 p.vertices = append(p.vertices, points...) 113 } 114 } 115 return p 116 } 117 118 // numVertices reports the total number of vertices in all loops. 119 func (p *LaxPolygon) numVertices() int { 120 if p.numLoops <= 1 { 121 return p.numVerts 122 } 123 return p.cumulativeVertices[p.numLoops] 124 } 125 126 // numLoopVertices reports the total number of vertices in the given loop. 127 func (p *LaxPolygon) numLoopVertices(i int) int { 128 if p.numLoops == 1 { 129 return p.numVerts 130 } 131 return p.cumulativeVertices[i+1] - p.cumulativeVertices[i] 132 } 133 134 // loopVertex returns the vertex from loop i at index j. 135 // 136 // This requires: 137 // 138 // 0 <= i < len(loops) 139 // 0 <= j < len(loop[i].vertices) 140 func (p *LaxPolygon) loopVertex(i, j int) Point { 141 if p.numLoops == 1 { 142 return p.vertices[j] 143 } 144 145 return p.vertices[p.cumulativeVertices[i]+j] 146 } 147 148 func (p *LaxPolygon) NumEdges() int { return p.numVertices() } 149 150 func (p *LaxPolygon) Edge(e int) Edge { 151 e1 := e + 1 152 if p.numLoops == 1 { 153 // wrap the end vertex if this is the last edge. 154 if e1 == p.numVerts { 155 e1 = 0 156 } 157 return Edge{p.vertices[e], p.vertices[e1]} 158 } 159 160 // TODO(roberts): If this turns out to be performance critical in tests 161 // incorporate the maxLinearSearchLoops like in C++. 162 163 // Check if e1 would cross a loop boundary in the set of all vertices. 164 nextLoop := 0 165 for p.cumulativeVertices[nextLoop] <= e { 166 nextLoop++ 167 } 168 169 // If so, wrap around to the first vertex of the loop. 170 if e1 == p.cumulativeVertices[nextLoop] { 171 e1 = p.cumulativeVertices[nextLoop-1] 172 } 173 174 return Edge{p.vertices[e], p.vertices[e1]} 175 } 176 177 func (p *LaxPolygon) Dimension() int { return 2 } 178 func (p *LaxPolygon) typeTag() typeTag { return typeTagLaxPolygon } 179 func (p *LaxPolygon) privateInterface() {} 180 func (p *LaxPolygon) IsEmpty() bool { return defaultShapeIsEmpty(p) } 181 func (p *LaxPolygon) IsFull() bool { return defaultShapeIsFull(p) } 182 func (p *LaxPolygon) ReferencePoint() ReferencePoint { return referencePointForShape(p) } 183 func (p *LaxPolygon) NumChains() int { return p.numLoops } 184 func (p *LaxPolygon) Chain(i int) Chain { 185 if p.numLoops == 1 { 186 return Chain{0, p.numVertices()} 187 } 188 start := p.cumulativeVertices[i] 189 return Chain{start, p.cumulativeVertices[i+1] - start} 190 } 191 192 func (p *LaxPolygon) ChainEdge(i, j int) Edge { 193 n := p.numLoopVertices(i) 194 k := 0 195 if j+1 != n { 196 k = j + 1 197 } 198 if p.numLoops == 1 { 199 return Edge{p.vertices[j], p.vertices[k]} 200 } 201 base := p.cumulativeVertices[i] 202 return Edge{p.vertices[base+j], p.vertices[base+k]} 203 } 204 205 func (p *LaxPolygon) ChainPosition(e int) ChainPosition { 206 if p.numLoops == 1 { 207 return ChainPosition{0, e} 208 } 209 210 // TODO(roberts): If this turns out to be performance critical in tests 211 // incorporate the maxLinearSearchLoops like in C++. 212 213 // Find the index of the first vertex of the loop following this one. 214 nextLoop := 1 215 for p.cumulativeVertices[nextLoop] <= e { 216 nextLoop++ 217 } 218 219 return ChainPosition{p.cumulativeVertices[nextLoop] - p.cumulativeVertices[1], e - p.cumulativeVertices[nextLoop-1]} 220 } 221 222 // TODO(roberts): Remaining to port from C++: 223 // EncodedLaxPolygon 224