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