1 // Copyright 2017 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 // CrossingType defines different ways of reporting edge intersections. 18 type CrossingType int 19 20 const ( 21 // CrossingTypeInterior reports intersections that occur at a point 22 // interior to both edges (i.e., not at a vertex). 23 CrossingTypeInterior CrossingType = iota 24 25 // CrossingTypeAll reports all intersections, even those where two edges 26 // intersect only because they share a common vertex. 27 CrossingTypeAll 28 29 // CrossingTypeNonAdjacent reports all intersections except for pairs of 30 // the form (AB, BC) where both edges are from the same ShapeIndex. 31 CrossingTypeNonAdjacent 32 ) 33 34 // rangeIterator is a wrapper over ShapeIndexIterator with extra methods 35 // that are useful for merging the contents of two or more ShapeIndexes. 36 type rangeIterator struct { 37 it *ShapeIndexIterator 38 // The min and max leaf cell ids covered by the current cell. If done() is 39 // true, these methods return a value larger than any valid cell id. 40 rangeMin CellID 41 rangeMax CellID 42 } 43 44 // newRangeIterator creates a new rangeIterator positioned at the first cell of the given index. 45 func newRangeIterator(index *ShapeIndex) *rangeIterator { 46 r := &rangeIterator{ 47 it: index.Iterator(), 48 } 49 r.refresh() 50 return r 51 } 52 53 func (r *rangeIterator) cellID() CellID { return r.it.CellID() } 54 func (r *rangeIterator) indexCell() *ShapeIndexCell { return r.it.IndexCell() } 55 func (r *rangeIterator) next() { r.it.Next(); r.refresh() } 56 func (r *rangeIterator) done() bool { return r.it.Done() } 57 58 // seekTo positions the iterator at the first cell that overlaps or follows 59 // the current range minimum of the target iterator, i.e. such that its 60 // rangeMax >= target.rangeMin. 61 func (r *rangeIterator) seekTo(target *rangeIterator) { 62 r.it.seek(target.rangeMin) 63 // If the current cell does not overlap target, it is possible that the 64 // previous cell is the one we are looking for. This can only happen when 65 // the previous cell contains target but has a smaller CellID. 66 if r.it.Done() || r.it.CellID().RangeMin() > target.rangeMax { 67 if r.it.Prev() && r.it.CellID().RangeMax() < target.cellID() { 68 r.it.Next() 69 } 70 } 71 r.refresh() 72 } 73 74 // seekBeyond positions the iterator at the first cell that follows the current 75 // range minimum of the target iterator. i.e. the first cell such that its 76 // rangeMin > target.rangeMax. 77 func (r *rangeIterator) seekBeyond(target *rangeIterator) { 78 r.it.seek(target.rangeMax.Next()) 79 if !r.it.Done() && r.it.CellID().RangeMin() <= target.rangeMax { 80 r.it.Next() 81 } 82 r.refresh() 83 } 84 85 // refresh updates the iterators min and max values. 86 func (r *rangeIterator) refresh() { 87 r.rangeMin = r.cellID().RangeMin() 88 r.rangeMax = r.cellID().RangeMax() 89 } 90 91 // referencePointForShape is a helper function for implementing various Shapes 92 // ReferencePoint functions. 93 // 94 // Given a shape consisting of closed polygonal loops, the interior of the 95 // shape is defined as the region to the left of all edges (which must be 96 // oriented consistently). This function then chooses an arbitrary point and 97 // returns true if that point is contained by the shape. 98 // 99 // Unlike Loop and Polygon, this method allows duplicate vertices and 100 // edges, which requires some extra care with definitions. The rule that we 101 // apply is that an edge and its reverse edge cancel each other: the result 102 // is the same as if that edge pair were not present. Therefore shapes that 103 // consist only of degenerate loop(s) are either empty or full; by convention, 104 // the shape is considered full if and only if it contains an empty loop (see 105 // laxPolygon for details). 106 // 107 // Determining whether a loop on the sphere contains a point is harder than 108 // the corresponding problem in 2D plane geometry. It cannot be implemented 109 // just by counting edge crossings because there is no such thing as a point 110 // at infinity that is guaranteed to be outside the loop. 111 // 112 // This function requires that the given Shape have an interior. 113 func referencePointForShape(shape Shape) ReferencePoint { 114 if shape.NumEdges() == 0 { 115 // A shape with no edges is defined to be full if and only if it 116 // contains at least one chain. 117 return OriginReferencePoint(shape.NumChains() > 0) 118 } 119 // Define a "matched" edge as one that can be paired with a corresponding 120 // reversed edge. Define a vertex as "balanced" if all of its edges are 121 // matched. In order to determine containment, we must find an unbalanced 122 // vertex. Often every vertex is unbalanced, so we start by trying an 123 // arbitrary vertex. 124 edge := shape.Edge(0) 125 126 if ref, ok := referencePointAtVertex(shape, edge.V0); ok { 127 return ref 128 } 129 130 // That didn't work, so now we do some extra work to find an unbalanced 131 // vertex (if any). Essentially we gather a list of edges and a list of 132 // reversed edges, and then sort them. The first edge that appears in one 133 // list but not the other is guaranteed to be unmatched. 134 n := shape.NumEdges() 135 var edges = make([]Edge, n) 136 var revEdges = make([]Edge, n) 137 for i := 0; i < n; i++ { 138 edge := shape.Edge(i) 139 edges[i] = edge 140 revEdges[i] = Edge{V0: edge.V1, V1: edge.V0} 141 } 142 143 sortEdges(edges) 144 sortEdges(revEdges) 145 146 for i := 0; i < n; i++ { 147 if edges[i].Cmp(revEdges[i]) == -1 { // edges[i] is unmatched 148 if ref, ok := referencePointAtVertex(shape, edges[i].V0); ok { 149 return ref 150 } 151 } 152 if revEdges[i].Cmp(edges[i]) == -1 { // revEdges[i] is unmatched 153 if ref, ok := referencePointAtVertex(shape, revEdges[i].V0); ok { 154 return ref 155 } 156 } 157 } 158 159 // All vertices are balanced, so this polygon is either empty or full except 160 // for degeneracies. By convention it is defined to be full if it contains 161 // any chain with no edges. 162 for i := 0; i < shape.NumChains(); i++ { 163 if shape.Chain(i).Length == 0 { 164 return OriginReferencePoint(true) 165 } 166 } 167 168 return OriginReferencePoint(false) 169 } 170 171 // referencePointAtVertex reports whether the given vertex is unbalanced, and 172 // returns a ReferencePoint indicating if the point is contained. 173 // Otherwise returns false. 174 func referencePointAtVertex(shape Shape, vTest Point) (ReferencePoint, bool) { 175 var ref ReferencePoint 176 177 // Let P be an unbalanced vertex. Vertex P is defined to be inside the 178 // region if the region contains a particular direction vector starting from 179 // P, namely the direction p.Ortho(). This can be calculated using 180 // ContainsVertexQuery. 181 182 containsQuery := NewContainsVertexQuery(vTest) 183 n := shape.NumEdges() 184 for e := 0; e < n; e++ { 185 edge := shape.Edge(e) 186 if edge.V0 == vTest { 187 containsQuery.AddEdge(edge.V1, 1) 188 } 189 if edge.V1 == vTest { 190 containsQuery.AddEdge(edge.V0, -1) 191 } 192 } 193 containsSign := containsQuery.ContainsVertex() 194 if containsSign == 0 { 195 return ref, false // There are no unmatched edges incident to this vertex. 196 } 197 ref.Point = vTest 198 ref.Contained = containsSign > 0 199 200 return ref, true 201 } 202 203 // containsBruteForce reports whether the given shape contains the given point. 204 // Most clients should not use this method, since its running time is linear in 205 // the number of shape edges. Instead clients should create a ShapeIndex and use 206 // ContainsPointQuery, since this strategy is much more efficient when many 207 // points need to be tested. 208 // 209 // Polygon boundaries are treated as being semi-open (see ContainsPointQuery 210 // and VertexModel for other options). 211 func containsBruteForce(shape Shape, point Point) bool { 212 if shape.Dimension() != 2 { 213 return false 214 } 215 216 refPoint := shape.ReferencePoint() 217 if refPoint.Point == point { 218 return refPoint.Contained 219 } 220 221 crosser := NewEdgeCrosser(refPoint.Point, point) 222 inside := refPoint.Contained 223 for e := 0; e < shape.NumEdges(); e++ { 224 edge := shape.Edge(e) 225 inside = inside != crosser.EdgeOrVertexCrossing(edge.V0, edge.V1) 226 } 227 return inside 228 } 229