gtsocial-umbx

contains_point_query.go (6328B)

---

 // 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