summaryrefslogtreecommitdiff
path: root/vendor/github.com/golang/geo/s2/contains_point_query.go
diff options
context:
space:
mode:
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.go190
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