gtsocial-umbx

shapeutil.go (8329B)

---

 // Copyright 2017 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
 
 // CrossingType defines different ways of reporting edge intersections.
 type CrossingType int
 
 const (
 	// CrossingTypeInterior reports intersections that occur at a point
 	// interior to both edges (i.e., not at a vertex).
 	CrossingTypeInterior CrossingType = iota
 
 	// CrossingTypeAll reports all intersections, even those where two edges
 	// intersect only because they share a common vertex.
 	CrossingTypeAll
 
 	// CrossingTypeNonAdjacent reports all intersections except for pairs of
 	// the form (AB, BC) where both edges are from the same ShapeIndex.
 	CrossingTypeNonAdjacent
 )
 
 // rangeIterator is a wrapper over ShapeIndexIterator with extra methods
 // that are useful for merging the contents of two or more ShapeIndexes.
 type rangeIterator struct {
 	it *ShapeIndexIterator
 	// The min and max leaf cell ids covered by the current cell. If done() is
 	// true, these methods return a value larger than any valid cell id.
 	rangeMin CellID
 	rangeMax CellID
 }
 
 // newRangeIterator creates a new rangeIterator positioned at the first cell of the given index.
 func newRangeIterator(index *ShapeIndex) *rangeIterator {
 	r := &rangeIterator{
 		it: index.Iterator(),
 	}
 	r.refresh()
 	return r
 }
 
 func (r *rangeIterator) cellID() CellID             { return r.it.CellID() }
 func (r *rangeIterator) indexCell() *ShapeIndexCell { return r.it.IndexCell() }
 func (r *rangeIterator) next()                      { r.it.Next(); r.refresh() }
 func (r *rangeIterator) done() bool                 { return r.it.Done() }
 
 // seekTo positions the iterator at the first cell that overlaps or follows
 // the current range minimum of the target iterator, i.e. such that its
 // rangeMax >= target.rangeMin.
 func (r *rangeIterator) seekTo(target *rangeIterator) {
 	r.it.seek(target.rangeMin)
 	// If the current cell does not overlap target, it is possible that the
 	// previous cell is the one we are looking for. This can only happen when
 	// the previous cell contains target but has a smaller CellID.
 	if r.it.Done() || r.it.CellID().RangeMin() > target.rangeMax {
 		if r.it.Prev() && r.it.CellID().RangeMax() < target.cellID() {
 			r.it.Next()
 		}
 	}
 	r.refresh()
 }
 
 // seekBeyond positions the iterator at the first cell that follows the current
 // range minimum of the target iterator. i.e. the first cell such that its
 // rangeMin > target.rangeMax.
 func (r *rangeIterator) seekBeyond(target *rangeIterator) {
 	r.it.seek(target.rangeMax.Next())
 	if !r.it.Done() && r.it.CellID().RangeMin() <= target.rangeMax {
 		r.it.Next()
 	}
 	r.refresh()
 }
 
 // refresh updates the iterators min and max values.
 func (r *rangeIterator) refresh() {
 	r.rangeMin = r.cellID().RangeMin()
 	r.rangeMax = r.cellID().RangeMax()
 }
 
 // referencePointForShape is a helper function for implementing various Shapes
 // ReferencePoint functions.
 //
 // Given a shape consisting of closed polygonal loops, the interior of the
 // shape is defined as the region to the left of all edges (which must be
 // oriented consistently). This function then chooses an arbitrary point and
 // returns true if that point is contained by the shape.
 //
 // Unlike Loop and Polygon, this method allows duplicate vertices and
 // edges, which requires some extra care with definitions. The rule that we
 // apply is that an edge and its reverse edge cancel each other: the result
 // is the same as if that edge pair were not present. Therefore shapes that
 // consist only of degenerate loop(s) are either empty or full; by convention,
 // the shape is considered full if and only if it contains an empty loop (see
 // laxPolygon for details).
 //
 // Determining whether a loop on the sphere contains a point is harder than
 // the corresponding problem in 2D plane geometry. It cannot be implemented
 // just by counting edge crossings because there is no such thing as a point
 // at infinity that is guaranteed to be outside the loop.
 //
 // This function requires that the given Shape have an interior.
 func referencePointForShape(shape Shape) ReferencePoint {
 	if shape.NumEdges() == 0 {
 		// A shape with no edges is defined to be full if and only if it
 		// contains at least one chain.
 		return OriginReferencePoint(shape.NumChains() > 0)
 	}
 	// Define a "matched" edge as one that can be paired with a corresponding
 	// reversed edge. Define a vertex as "balanced" if all of its edges are
 	// matched. In order to determine containment, we must find an unbalanced
 	// vertex. Often every vertex is unbalanced, so we start by trying an
 	// arbitrary vertex.
 	edge := shape.Edge(0)
 
 	if ref, ok := referencePointAtVertex(shape, edge.V0); ok {
 		return ref
 	}
 
 	// That didn't work, so now we do some extra work to find an unbalanced
 	// vertex (if any). Essentially we gather a list of edges and a list of
 	// reversed edges, and then sort them. The first edge that appears in one
 	// list but not the other is guaranteed to be unmatched.
 	n := shape.NumEdges()
 	var edges = make([]Edge, n)
 	var revEdges = make([]Edge, n)
 	for i := 0; i < n; i++ {
 		edge := shape.Edge(i)
 		edges[i] = edge
 		revEdges[i] = Edge{V0: edge.V1, V1: edge.V0}
 	}
 
 	sortEdges(edges)
 	sortEdges(revEdges)
 
 	for i := 0; i < n; i++ {
 		if edges[i].Cmp(revEdges[i]) == -1 { // edges[i] is unmatched
 			if ref, ok := referencePointAtVertex(shape, edges[i].V0); ok {
 				return ref
 			}
 		}
 		if revEdges[i].Cmp(edges[i]) == -1 { // revEdges[i] is unmatched
 			if ref, ok := referencePointAtVertex(shape, revEdges[i].V0); ok {
 				return ref
 			}
 		}
 	}
 
 	// All vertices are balanced, so this polygon is either empty or full except
 	// for degeneracies. By convention it is defined to be full if it contains
 	// any chain with no edges.
 	for i := 0; i < shape.NumChains(); i++ {
 		if shape.Chain(i).Length == 0 {
 			return OriginReferencePoint(true)
 		}
 	}
 
 	return OriginReferencePoint(false)
 }
 
 // referencePointAtVertex reports whether the given vertex is unbalanced, and
 // returns a ReferencePoint indicating if the point is contained.
 // Otherwise returns false.
 func referencePointAtVertex(shape Shape, vTest Point) (ReferencePoint, bool) {
 	var ref ReferencePoint
 
 	// Let P be an unbalanced vertex. Vertex P is defined to be inside the
 	// region if the region contains a particular direction vector starting from
 	// P, namely the direction p.Ortho(). This can be calculated using
 	// ContainsVertexQuery.
 
 	containsQuery := NewContainsVertexQuery(vTest)
 	n := shape.NumEdges()
 	for e := 0; e < n; e++ {
 		edge := shape.Edge(e)
 		if edge.V0 == vTest {
 			containsQuery.AddEdge(edge.V1, 1)
 		}
 		if edge.V1 == vTest {
 			containsQuery.AddEdge(edge.V0, -1)
 		}
 	}
 	containsSign := containsQuery.ContainsVertex()
 	if containsSign == 0 {
 		return ref, false // There are no unmatched edges incident to this vertex.
 	}
 	ref.Point = vTest
 	ref.Contained = containsSign > 0
 
 	return ref, true
 }
 
 // containsBruteForce reports whether the given shape contains the given point.
 // Most clients should not use this method, since its running time is linear in
 // the number of shape edges. Instead clients should create a ShapeIndex and use
 // ContainsPointQuery, since this strategy is much more efficient when many
 // points need to be tested.
 //
 // Polygon boundaries are treated as being semi-open (see ContainsPointQuery
 // and VertexModel for other options).
 func containsBruteForce(shape Shape, point Point) bool {
 	if shape.Dimension() != 2 {
 		return false
 	}
 
 	refPoint := shape.ReferencePoint()
 	if refPoint.Point == point {
 		return refPoint.Contained
 	}
 
 	crosser := NewEdgeCrosser(refPoint.Point, point)
 	inside := refPoint.Contained
 	for e := 0; e < shape.NumEdges(); e++ {
 		edge := shape.Edge(e)
 		inside = inside != crosser.EdgeOrVertexCrossing(edge.V0, edge.V1)
 	}
 	return inside
 }