1 files changed, 190 insertions, 0 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
new file mode 100644
index 000000000..3026f3601
--- /dev/null
+++ b/vendor/github.com/golang/geo/s2/contains_point_query.go
@@ -0,0 +1,190 @@
+// 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