diff options
Diffstat (limited to 'vendor/github.com/golang/geo/s2/contains_point_query.go')
-rw-r--r-- | vendor/github.com/golang/geo/s2/contains_point_query.go | 190 |
1 files changed, 0 insertions, 190 deletions
diff --git a/vendor/github.com/golang/geo/s2/contains_point_query.go b/vendor/github.com/golang/geo/s2/contains_point_query.go deleted file mode 100644 index 3026f3601..000000000 --- a/vendor/github.com/golang/geo/s2/contains_point_query.go +++ /dev/null @@ -1,190 +0,0 @@ -// Copyright 2018 Google Inc. All rights reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package s2 - -// VertexModel defines whether shapes are considered to contain their vertices. -// Note that these definitions differ from the ones used by BooleanOperation. -// -// Note that points other than vertices are never contained by polylines. -// If you want need this behavior, use ClosestEdgeQuery's IsDistanceLess -// with a suitable distance threshold instead. -type VertexModel int - -const ( - // VertexModelOpen means no shapes contain their vertices (not even - // points). Therefore Contains(Point) returns true if and only if the - // point is in the interior of some polygon. - VertexModelOpen VertexModel = iota - - // VertexModelSemiOpen means that polygon point containment is defined - // such that if several polygons tile the region around a vertex, then - // exactly one of those polygons contains that vertex. Points and - // polylines still do not contain any vertices. - VertexModelSemiOpen - - // VertexModelClosed means all shapes contain their vertices (including - // points and polylines). - VertexModelClosed -) - -// ContainsPointQuery determines whether one or more shapes in a ShapeIndex -// contain a given Point. The ShapeIndex may contain any number of points, -// polylines, and/or polygons (possibly overlapping). Shape boundaries may be -// modeled as Open, SemiOpen, or Closed (this affects whether or not shapes are -// considered to contain their vertices). -// -// This type is not safe for concurrent use. -// -// However, note that if you need to do a large number of point containment -// tests, it is more efficient to re-use the query rather than creating a new -// one each time. -type ContainsPointQuery struct { - model VertexModel - index *ShapeIndex - iter *ShapeIndexIterator -} - -// NewContainsPointQuery creates a new instance of the ContainsPointQuery for the index -// and given vertex model choice. -func NewContainsPointQuery(index *ShapeIndex, model VertexModel) *ContainsPointQuery { - return &ContainsPointQuery{ - index: index, - model: model, - iter: index.Iterator(), - } -} - -// Contains reports whether any shape in the queries index contains the point p -// under the queries vertex model (Open, SemiOpen, or Closed). -func (q *ContainsPointQuery) Contains(p Point) bool { - if !q.iter.LocatePoint(p) { - return false - } - - cell := q.iter.IndexCell() - for _, clipped := range cell.shapes { - if q.shapeContains(clipped, q.iter.Center(), p) { - return true - } - } - return false -} - -// shapeContains reports whether the clippedShape from the iterator's center position contains -// the given point. -func (q *ContainsPointQuery) shapeContains(clipped *clippedShape, center, p Point) bool { - inside := clipped.containsCenter - numEdges := clipped.numEdges() - if numEdges <= 0 { - return inside - } - - shape := q.index.Shape(clipped.shapeID) - if shape.Dimension() != 2 { - // Points and polylines can be ignored unless the vertex model is Closed. - if q.model != VertexModelClosed { - return false - } - - // Otherwise, the point is contained if and only if it matches a vertex. - for _, edgeID := range clipped.edges { - edge := shape.Edge(edgeID) - if edge.V0 == p || edge.V1 == p { - return true - } - } - return false - } - - // Test containment by drawing a line segment from the cell center to the - // given point and counting edge crossings. - crosser := NewEdgeCrosser(center, p) - for _, edgeID := range clipped.edges { - edge := shape.Edge(edgeID) - sign := crosser.CrossingSign(edge.V0, edge.V1) - if sign == DoNotCross { - continue - } - if sign == MaybeCross { - // For the Open and Closed models, check whether p is a vertex. - if q.model != VertexModelSemiOpen && (edge.V0 == p || edge.V1 == p) { - return (q.model == VertexModelClosed) - } - // C++ plays fast and loose with the int <-> bool conversions here. - if VertexCrossing(crosser.a, crosser.b, edge.V0, edge.V1) { - sign = Cross - } else { - sign = DoNotCross - } - } - inside = inside != (sign == Cross) - } - - return inside -} - -// ShapeContains reports whether the given shape contains the point under this -// queries vertex model (Open, SemiOpen, or Closed). -// -// This requires the shape belongs to this queries index. -func (q *ContainsPointQuery) ShapeContains(shape Shape, p Point) bool { - if !q.iter.LocatePoint(p) { - return false - } - - clipped := q.iter.IndexCell().findByShapeID(q.index.idForShape(shape)) - if clipped == nil { - return false - } - return q.shapeContains(clipped, q.iter.Center(), p) -} - -// shapeVisitorFunc is a type of function that can be called against shaped in an index. -type shapeVisitorFunc func(shape Shape) bool - -// visitContainingShapes visits all shapes in the given index that contain the -// given point p, terminating early if the given visitor function returns false, -// in which case visitContainingShapes returns false. Each shape is -// visited at most once. -func (q *ContainsPointQuery) visitContainingShapes(p Point, f shapeVisitorFunc) bool { - // This function returns false only if the algorithm terminates early - // because the visitor function returned false. - if !q.iter.LocatePoint(p) { - return true - } - - cell := q.iter.IndexCell() - for _, clipped := range cell.shapes { - if q.shapeContains(clipped, q.iter.Center(), p) && - !f(q.index.Shape(clipped.shapeID)) { - return false - } - } - return true -} - -// ContainingShapes returns a slice of all shapes that contain the given point. -func (q *ContainsPointQuery) ContainingShapes(p Point) []Shape { - var shapes []Shape - q.visitContainingShapes(p, func(shape Shape) bool { - shapes = append(shapes, shape) - return true - }) - return shapes -} - -// TODO(roberts): Remaining methods from C++ -// type edgeVisitorFunc func(shape ShapeEdge) bool -// func (q *ContainsPointQuery) visitIncidentEdges(p Point, v edgeVisitorFunc) bool |