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 // VertexModel defines whether shapes are considered to contain their vertices. 18 // Note that these definitions differ from the ones used by BooleanOperation. 19 // 20 // Note that points other than vertices are never contained by polylines. 21 // If you want need this behavior, use ClosestEdgeQuery's IsDistanceLess 22 // with a suitable distance threshold instead. 23 type VertexModel int 24 25 const ( 26 // VertexModelOpen means no shapes contain their vertices (not even 27 // points). Therefore Contains(Point) returns true if and only if the 28 // point is in the interior of some polygon. 29 VertexModelOpen VertexModel = iota 30 31 // VertexModelSemiOpen means that polygon point containment is defined 32 // such that if several polygons tile the region around a vertex, then 33 // exactly one of those polygons contains that vertex. Points and 34 // polylines still do not contain any vertices. 35 VertexModelSemiOpen 36 37 // VertexModelClosed means all shapes contain their vertices (including 38 // points and polylines). 39 VertexModelClosed 40 ) 41 42 // ContainsPointQuery determines whether one or more shapes in a ShapeIndex 43 // contain a given Point. The ShapeIndex may contain any number of points, 44 // polylines, and/or polygons (possibly overlapping). Shape boundaries may be 45 // modeled as Open, SemiOpen, or Closed (this affects whether or not shapes are 46 // considered to contain their vertices). 47 // 48 // This type is not safe for concurrent use. 49 // 50 // However, note that if you need to do a large number of point containment 51 // tests, it is more efficient to re-use the query rather than creating a new 52 // one each time. 53 type ContainsPointQuery struct { 54 model VertexModel 55 index *ShapeIndex 56 iter *ShapeIndexIterator 57 } 58 59 // NewContainsPointQuery creates a new instance of the ContainsPointQuery for the index 60 // and given vertex model choice. 61 func NewContainsPointQuery(index *ShapeIndex, model VertexModel) *ContainsPointQuery { 62 return &ContainsPointQuery{ 63 index: index, 64 model: model, 65 iter: index.Iterator(), 66 } 67 } 68 69 // Contains reports whether any shape in the queries index contains the point p 70 // under the queries vertex model (Open, SemiOpen, or Closed). 71 func (q *ContainsPointQuery) Contains(p Point) bool { 72 if !q.iter.LocatePoint(p) { 73 return false 74 } 75 76 cell := q.iter.IndexCell() 77 for _, clipped := range cell.shapes { 78 if q.shapeContains(clipped, q.iter.Center(), p) { 79 return true 80 } 81 } 82 return false 83 } 84 85 // shapeContains reports whether the clippedShape from the iterator's center position contains 86 // the given point. 87 func (q *ContainsPointQuery) shapeContains(clipped *clippedShape, center, p Point) bool { 88 inside := clipped.containsCenter 89 numEdges := clipped.numEdges() 90 if numEdges <= 0 { 91 return inside 92 } 93 94 shape := q.index.Shape(clipped.shapeID) 95 if shape.Dimension() != 2 { 96 // Points and polylines can be ignored unless the vertex model is Closed. 97 if q.model != VertexModelClosed { 98 return false 99 } 100 101 // Otherwise, the point is contained if and only if it matches a vertex. 102 for _, edgeID := range clipped.edges { 103 edge := shape.Edge(edgeID) 104 if edge.V0 == p || edge.V1 == p { 105 return true 106 } 107 } 108 return false 109 } 110 111 // Test containment by drawing a line segment from the cell center to the 112 // given point and counting edge crossings. 113 crosser := NewEdgeCrosser(center, p) 114 for _, edgeID := range clipped.edges { 115 edge := shape.Edge(edgeID) 116 sign := crosser.CrossingSign(edge.V0, edge.V1) 117 if sign == DoNotCross { 118 continue 119 } 120 if sign == MaybeCross { 121 // For the Open and Closed models, check whether p is a vertex. 122 if q.model != VertexModelSemiOpen && (edge.V0 == p || edge.V1 == p) { 123 return (q.model == VertexModelClosed) 124 } 125 // C++ plays fast and loose with the int <-> bool conversions here. 126 if VertexCrossing(crosser.a, crosser.b, edge.V0, edge.V1) { 127 sign = Cross 128 } else { 129 sign = DoNotCross 130 } 131 } 132 inside = inside != (sign == Cross) 133 } 134 135 return inside 136 } 137 138 // ShapeContains reports whether the given shape contains the point under this 139 // queries vertex model (Open, SemiOpen, or Closed). 140 // 141 // This requires the shape belongs to this queries index. 142 func (q *ContainsPointQuery) ShapeContains(shape Shape, p Point) bool { 143 if !q.iter.LocatePoint(p) { 144 return false 145 } 146 147 clipped := q.iter.IndexCell().findByShapeID(q.index.idForShape(shape)) 148 if clipped == nil { 149 return false 150 } 151 return q.shapeContains(clipped, q.iter.Center(), p) 152 } 153 154 // shapeVisitorFunc is a type of function that can be called against shaped in an index. 155 type shapeVisitorFunc func(shape Shape) bool 156 157 // visitContainingShapes visits all shapes in the given index that contain the 158 // given point p, terminating early if the given visitor function returns false, 159 // in which case visitContainingShapes returns false. Each shape is 160 // visited at most once. 161 func (q *ContainsPointQuery) visitContainingShapes(p Point, f shapeVisitorFunc) bool { 162 // This function returns false only if the algorithm terminates early 163 // because the visitor function returned false. 164 if !q.iter.LocatePoint(p) { 165 return true 166 } 167 168 cell := q.iter.IndexCell() 169 for _, clipped := range cell.shapes { 170 if q.shapeContains(clipped, q.iter.Center(), p) && 171 !f(q.index.Shape(clipped.shapeID)) { 172 return false 173 } 174 } 175 return true 176 } 177 178 // ContainingShapes returns a slice of all shapes that contain the given point. 179 func (q *ContainsPointQuery) ContainingShapes(p Point) []Shape { 180 var shapes []Shape 181 q.visitContainingShapes(p, func(shape Shape) bool { 182 shapes = append(shapes, shape) 183 return true 184 }) 185 return shapes 186 } 187 188 // TODO(roberts): Remaining methods from C++ 189 // type edgeVisitorFunc func(shape ShapeEdge) bool 190 // func (q *ContainsPointQuery) visitIncidentEdges(p Point, v edgeVisitorFunc) bool 191