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 import ( 18 "sort" 19 ) 20 21 // Edge represents a geodesic edge consisting of two vertices. Zero-length edges are 22 // allowed, and can be used to represent points. 23 type Edge struct { 24 V0, V1 Point 25 } 26 27 // Cmp compares the two edges using the underlying Points Cmp method and returns 28 // 29 // -1 if e < other 30 // 0 if e == other 31 // +1 if e > other 32 // 33 // The two edges are compared by first vertex, and then by the second vertex. 34 func (e Edge) Cmp(other Edge) int { 35 if v0cmp := e.V0.Cmp(other.V0.Vector); v0cmp != 0 { 36 return v0cmp 37 } 38 return e.V1.Cmp(other.V1.Vector) 39 } 40 41 // sortEdges sorts the slice of Edges in place. 42 func sortEdges(e []Edge) { 43 sort.Sort(edges(e)) 44 } 45 46 // edges implements the Sort interface for slices of Edge. 47 type edges []Edge 48 49 func (e edges) Len() int { return len(e) } 50 func (e edges) Swap(i, j int) { e[i], e[j] = e[j], e[i] } 51 func (e edges) Less(i, j int) bool { return e[i].Cmp(e[j]) == -1 } 52 53 // ShapeEdgeID is a unique identifier for an Edge within an ShapeIndex, 54 // consisting of a (shapeID, edgeID) pair. 55 type ShapeEdgeID struct { 56 ShapeID int32 57 EdgeID int32 58 } 59 60 // Cmp compares the two ShapeEdgeIDs and returns 61 // 62 // -1 if s < other 63 // 0 if s == other 64 // +1 if s > other 65 // 66 // The two are compared first by shape id and then by edge id. 67 func (s ShapeEdgeID) Cmp(other ShapeEdgeID) int { 68 switch { 69 case s.ShapeID < other.ShapeID: 70 return -1 71 case s.ShapeID > other.ShapeID: 72 return 1 73 } 74 switch { 75 case s.EdgeID < other.EdgeID: 76 return -1 77 case s.EdgeID > other.EdgeID: 78 return 1 79 } 80 return 0 81 } 82 83 // ShapeEdge represents a ShapeEdgeID with the two endpoints of that Edge. 84 type ShapeEdge struct { 85 ID ShapeEdgeID 86 Edge Edge 87 } 88 89 // Chain represents a range of edge IDs corresponding to a chain of connected 90 // edges, specified as a (start, length) pair. The chain is defined to consist of 91 // edge IDs {start, start + 1, ..., start + length - 1}. 92 type Chain struct { 93 Start, Length int 94 } 95 96 // ChainPosition represents the position of an edge within a given edge chain, 97 // specified as a (chainID, offset) pair. Chains are numbered sequentially 98 // starting from zero, and offsets are measured from the start of each chain. 99 type ChainPosition struct { 100 ChainID, Offset int 101 } 102 103 // A ReferencePoint consists of a point and a boolean indicating whether the point 104 // is contained by a particular shape. 105 type ReferencePoint struct { 106 Point Point 107 Contained bool 108 } 109 110 // OriginReferencePoint returns a ReferencePoint with the given value for 111 // contained and the origin point. It should be used when all points or no 112 // points are contained. 113 func OriginReferencePoint(contained bool) ReferencePoint { 114 return ReferencePoint{Point: OriginPoint(), Contained: contained} 115 } 116 117 // typeTag is a 32-bit tag that can be used to identify the type of an encoded 118 // Shape. All encodable types have a non-zero type tag. The tag associated with 119 type typeTag uint32 120 121 const ( 122 // Indicates that a given Shape type cannot be encoded. 123 typeTagNone typeTag = 0 124 typeTagPolygon typeTag = 1 125 typeTagPolyline typeTag = 2 126 typeTagPointVector typeTag = 3 127 typeTagLaxPolyline typeTag = 4 128 typeTagLaxPolygon typeTag = 5 129 130 // The minimum allowable tag for future user-defined Shape types. 131 typeTagMinUser typeTag = 8192 132 ) 133 134 // Shape represents polygonal geometry in a flexible way. It is organized as a 135 // collection of edges that optionally defines an interior. All geometry 136 // represented by a given Shape must have the same dimension, which means that 137 // an Shape can represent either a set of points, a set of polylines, or a set 138 // of polygons. 139 // 140 // Shape is defined as an interface in order to give clients control over the 141 // underlying data representation. Sometimes an Shape does not have any data of 142 // its own, but instead wraps some other type. 143 // 144 // Shape operations are typically defined on a ShapeIndex rather than 145 // individual shapes. An ShapeIndex is simply a collection of Shapes, 146 // possibly of different dimensions (e.g. 10 points and 3 polygons), organized 147 // into a data structure for efficient edge access. 148 // 149 // The edges of a Shape are indexed by a contiguous range of edge IDs 150 // starting at 0. The edges are further subdivided into chains, where each 151 // chain consists of a sequence of edges connected end-to-end (a polyline). 152 // For example, a Shape representing two polylines AB and CDE would have 153 // three edges (AB, CD, DE) grouped into two chains: (AB) and (CD, DE). 154 // Similarly, an Shape representing 5 points would have 5 chains consisting 155 // of one edge each. 156 // 157 // Shape has methods that allow edges to be accessed either using the global 158 // numbering (edge ID) or within a particular chain. The global numbering is 159 // sufficient for most purposes, but the chain representation is useful for 160 // certain algorithms such as intersection (see BooleanOperation). 161 type Shape interface { 162 // NumEdges returns the number of edges in this shape. 163 NumEdges() int 164 165 // Edge returns the edge for the given edge index. 166 Edge(i int) Edge 167 168 // ReferencePoint returns an arbitrary reference point for the shape. (The 169 // containment boolean value must be false for shapes that do not have an interior.) 170 // 171 // This reference point may then be used to compute the containment of other 172 // points by counting edge crossings. 173 ReferencePoint() ReferencePoint 174 175 // NumChains reports the number of contiguous edge chains in the shape. 176 // For example, a shape whose edges are [AB, BC, CD, AE, EF] would consist 177 // of two chains (AB,BC,CD and AE,EF). Every chain is assigned a chain Id 178 // numbered sequentially starting from zero. 179 // 180 // Note that it is always acceptable to implement this method by returning 181 // NumEdges, i.e. every chain consists of a single edge, but this may 182 // reduce the efficiency of some algorithms. 183 NumChains() int 184 185 // Chain returns the range of edge IDs corresponding to the given edge chain. 186 // Edge chains must form contiguous, non-overlapping ranges that cover 187 // the entire range of edge IDs. This is spelled out more formally below: 188 // 189 // 0 <= i < NumChains() 190 // Chain(i).length > 0, for all i 191 // Chain(0).start == 0 192 // Chain(i).start + Chain(i).length == Chain(i+1).start, for i < NumChains()-1 193 // Chain(i).start + Chain(i).length == NumEdges(), for i == NumChains()-1 194 Chain(chainID int) Chain 195 196 // ChainEdgeReturns the edge at offset "offset" within edge chain "chainID". 197 // Equivalent to "shape.Edge(shape.Chain(chainID).start + offset)" 198 // but more efficient. 199 ChainEdge(chainID, offset int) Edge 200 201 // ChainPosition finds the chain containing the given edge, and returns the 202 // position of that edge as a ChainPosition(chainID, offset) pair. 203 // 204 // shape.Chain(pos.chainID).start + pos.offset == edgeID 205 // shape.Chain(pos.chainID+1).start > edgeID 206 // 207 // where pos == shape.ChainPosition(edgeID). 208 ChainPosition(edgeID int) ChainPosition 209 210 // Dimension returns the dimension of the geometry represented by this shape, 211 // either 0, 1 or 2 for point, polyline and polygon geometry respectively. 212 // 213 // 0 - Point geometry. Each point is represented as a degenerate edge. 214 // 215 // 1 - Polyline geometry. Polyline edges may be degenerate. A shape may 216 // represent any number of polylines. Polylines edges may intersect. 217 // 218 // 2 - Polygon geometry. Edges should be oriented such that the polygon 219 // interior is always on the left. In theory the edges may be returned 220 // in any order, but typically the edges are organized as a collection 221 // of edge chains where each chain represents one polygon loop. 222 // Polygons may have degeneracies (e.g., degenerate edges or sibling 223 // pairs consisting of an edge and its corresponding reversed edge). 224 // A polygon loop may also be full (containing all points on the 225 // sphere); by convention this is represented as a chain with no edges. 226 // (See laxPolygon for details.) 227 // 228 // This method allows degenerate geometry of different dimensions 229 // to be distinguished, e.g. it allows a point to be distinguished from a 230 // polyline or polygon that has been simplified to a single point. 231 Dimension() int 232 233 // IsEmpty reports whether the Shape contains no points. (Note that the full 234 // polygon is represented as a chain with zero edges.) 235 IsEmpty() bool 236 237 // IsFull reports whether the Shape contains all points on the sphere. 238 IsFull() bool 239 240 // typeTag returns a value that can be used to identify the type of an 241 // encoded Shape. 242 typeTag() typeTag 243 244 // We do not support implementations of this interface outside this package. 245 privateInterface() 246 } 247 248 // defaultShapeIsEmpty reports whether this shape contains no points. 249 func defaultShapeIsEmpty(s Shape) bool { 250 return s.NumEdges() == 0 && (s.Dimension() != 2 || s.NumChains() == 0) 251 } 252 253 // defaultShapeIsFull reports whether this shape contains all points on the sphere. 254 func defaultShapeIsFull(s Shape) bool { 255 return s.NumEdges() == 0 && s.Dimension() == 2 && s.NumChains() > 0 256 } 257 258 // A minimal check for types that should satisfy the Shape interface. 259 var ( 260 _ Shape = &Loop{} 261 _ Shape = &Polygon{} 262 _ Shape = &Polyline{} 263 ) 264