diff options
Diffstat (limited to 'vendor/github.com/golang/geo/s2/edge_crosser.go')
| -rw-r--r-- | vendor/github.com/golang/geo/s2/edge_crosser.go | 227 |
1 files changed, 0 insertions, 227 deletions
diff --git a/vendor/github.com/golang/geo/s2/edge_crosser.go b/vendor/github.com/golang/geo/s2/edge_crosser.go deleted file mode 100644 index 69c6da6b9..000000000 --- a/vendor/github.com/golang/geo/s2/edge_crosser.go +++ /dev/null @@ -1,227 +0,0 @@ -// 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 - -import ( - "math" -) - -// EdgeCrosser allows edges to be efficiently tested for intersection with a -// given fixed edge AB. It is especially efficient when testing for -// intersection with an edge chain connecting vertices v0, v1, v2, ... -// -// Example usage: -// -// func CountIntersections(a, b Point, edges []Edge) int { -// count := 0 -// crosser := NewEdgeCrosser(a, b) -// for _, edge := range edges { -// if crosser.CrossingSign(&edge.First, &edge.Second) != DoNotCross { -// count++ -// } -// } -// return count -// } -// -type EdgeCrosser struct { - a Point - b Point - aXb Point - - // To reduce the number of calls to expensiveSign, we compute an - // outward-facing tangent at A and B if necessary. If the plane - // perpendicular to one of these tangents separates AB from CD (i.e., one - // edge on each side) then there is no intersection. - aTangent Point // Outward-facing tangent at A. - bTangent Point // Outward-facing tangent at B. - - // The fields below are updated for each vertex in the chain. - c Point // Previous vertex in the vertex chain. - acb Direction // The orientation of triangle ACB. -} - -// NewEdgeCrosser returns an EdgeCrosser with the fixed edge AB. -func NewEdgeCrosser(a, b Point) *EdgeCrosser { - norm := a.PointCross(b) - return &EdgeCrosser{ - a: a, - b: b, - aXb: Point{a.Cross(b.Vector)}, - aTangent: Point{a.Cross(norm.Vector)}, - bTangent: Point{norm.Cross(b.Vector)}, - } -} - -// CrossingSign reports whether the edge AB intersects the edge CD. If any two -// vertices from different edges are the same, returns MaybeCross. If either edge -// is degenerate (A == B or C == D), returns either DoNotCross or MaybeCross. -// -// Properties of CrossingSign: -// -// (1) CrossingSign(b,a,c,d) == CrossingSign(a,b,c,d) -// (2) CrossingSign(c,d,a,b) == CrossingSign(a,b,c,d) -// (3) CrossingSign(a,b,c,d) == MaybeCross if a==c, a==d, b==c, b==d -// (3) CrossingSign(a,b,c,d) == DoNotCross or MaybeCross if a==b or c==d -// -// Note that if you want to check an edge against a chain of other edges, -// it is slightly more efficient to use the single-argument version -// ChainCrossingSign below. -func (e *EdgeCrosser) CrossingSign(c, d Point) Crossing { - if c != e.c { - e.RestartAt(c) - } - return e.ChainCrossingSign(d) -} - -// EdgeOrVertexCrossing reports whether if CrossingSign(c, d) > 0, or AB and -// CD share a vertex and VertexCrossing(a, b, c, d) is true. -// -// This method extends the concept of a "crossing" to the case where AB -// and CD have a vertex in common. The two edges may or may not cross, -// according to the rules defined in VertexCrossing above. The rules -// are designed so that point containment tests can be implemented simply -// by counting edge crossings. Similarly, determining whether one edge -// chain crosses another edge chain can be implemented by counting. -func (e *EdgeCrosser) EdgeOrVertexCrossing(c, d Point) bool { - if c != e.c { - e.RestartAt(c) - } - return e.EdgeOrVertexChainCrossing(d) -} - -// NewChainEdgeCrosser is a convenience constructor that uses AB as the fixed edge, -// and C as the first vertex of the vertex chain (equivalent to calling RestartAt(c)). -// -// You don't need to use this or any of the chain functions unless you're trying to -// squeeze out every last drop of performance. Essentially all you are saving is a test -// whether the first vertex of the current edge is the same as the second vertex of the -// previous edge. -func NewChainEdgeCrosser(a, b, c Point) *EdgeCrosser { - e := NewEdgeCrosser(a, b) - e.RestartAt(c) - return e -} - -// RestartAt sets the current point of the edge crosser to be c. -// Call this method when your chain 'jumps' to a new place. -// The argument must point to a value that persists until the next call. -func (e *EdgeCrosser) RestartAt(c Point) { - e.c = c - e.acb = -triageSign(e.a, e.b, e.c) -} - -// ChainCrossingSign is like CrossingSign, but uses the last vertex passed to one of -// the crossing methods (or RestartAt) as the first vertex of the current edge. -func (e *EdgeCrosser) ChainCrossingSign(d Point) Crossing { - // For there to be an edge crossing, the triangles ACB, CBD, BDA, DAC must - // all be oriented the same way (CW or CCW). We keep the orientation of ACB - // as part of our state. When each new point D arrives, we compute the - // orientation of BDA and check whether it matches ACB. This checks whether - // the points C and D are on opposite sides of the great circle through AB. - - // Recall that triageSign is invariant with respect to rotating its - // arguments, i.e. ABD has the same orientation as BDA. - bda := triageSign(e.a, e.b, d) - if e.acb == -bda && bda != Indeterminate { - // The most common case -- triangles have opposite orientations. Save the - // current vertex D as the next vertex C, and also save the orientation of - // the new triangle ACB (which is opposite to the current triangle BDA). - e.c = d - e.acb = -bda - return DoNotCross - } - return e.crossingSign(d, bda) -} - -// EdgeOrVertexChainCrossing is like EdgeOrVertexCrossing, but uses the last vertex -// passed to one of the crossing methods (or RestartAt) as the first vertex of the current edge. -func (e *EdgeCrosser) EdgeOrVertexChainCrossing(d Point) bool { - // We need to copy e.c since it is clobbered by ChainCrossingSign. - c := e.c - switch e.ChainCrossingSign(d) { - case DoNotCross: - return false - case Cross: - return true - } - return VertexCrossing(e.a, e.b, c, d) -} - -// crossingSign handle the slow path of CrossingSign. -func (e *EdgeCrosser) crossingSign(d Point, bda Direction) Crossing { - // Compute the actual result, and then save the current vertex D as the next - // vertex C, and save the orientation of the next triangle ACB (which is - // opposite to the current triangle BDA). - defer func() { - e.c = d - e.acb = -bda - }() - - // At this point, a very common situation is that A,B,C,D are four points on - // a line such that AB does not overlap CD. (For example, this happens when - // a line or curve is sampled finely, or when geometry is constructed by - // computing the union of S2CellIds.) Most of the time, we can determine - // that AB and CD do not intersect using the two outward-facing - // tangents at A and B (parallel to AB) and testing whether AB and CD are on - // opposite sides of the plane perpendicular to one of these tangents. This - // is moderately expensive but still much cheaper than expensiveSign. - - // The error in RobustCrossProd is insignificant. The maximum error in - // the call to CrossProd (i.e., the maximum norm of the error vector) is - // (0.5 + 1/sqrt(3)) * dblEpsilon. The maximum error in each call to - // DotProd below is dblEpsilon. (There is also a small relative error - // term that is insignificant because we are comparing the result against a - // constant that is very close to zero.) - maxError := (1.5 + 1/math.Sqrt(3)) * dblEpsilon - if (e.c.Dot(e.aTangent.Vector) > maxError && d.Dot(e.aTangent.Vector) > maxError) || (e.c.Dot(e.bTangent.Vector) > maxError && d.Dot(e.bTangent.Vector) > maxError) { - return DoNotCross - } - - // Otherwise, eliminate the cases where two vertices from different edges are - // equal. (These cases could be handled in the code below, but we would rather - // avoid calling ExpensiveSign if possible.) - if e.a == e.c || e.a == d || e.b == e.c || e.b == d { - return MaybeCross - } - - // Eliminate the cases where an input edge is degenerate. (Note that in - // most cases, if CD is degenerate then this method is not even called - // because acb and bda have different signs.) - if e.a == e.b || e.c == d { - return DoNotCross - } - - // Otherwise it's time to break out the big guns. - if e.acb == Indeterminate { - e.acb = -expensiveSign(e.a, e.b, e.c) - } - if bda == Indeterminate { - bda = expensiveSign(e.a, e.b, d) - } - - if bda != e.acb { - return DoNotCross - } - - cbd := -RobustSign(e.c, d, e.b) - if cbd != e.acb { - return DoNotCross - } - dac := RobustSign(e.c, d, e.a) - if dac != e.acb { - return DoNotCross - } - return Cross -} |