// edgeCrossesCell reports whether the current edge of loop A has any crossings with
// edges of the index cell of loop B.
323832
func (l *loopCrosser) edgeCrossesCell(bClipped *clippedShape) bool {
	// Test the current edge of A against all edges of bClipped
	bNumEdges := bClipped.numEdges()
	for j := 0; j < bNumEdges; j++ {
		bj := bClipped.edges[j]
		if bj != l.bjPrev+1 {
			l.crosser.RestartAt(l.b.Vertex(bj))
		}
		l.bjPrev = bj
		if crossing := l.crosser.ChainCrossingSign(l.b.Vertex(bj + 1)); crossing == DoNotCross {
			continue
		} else if crossing == Cross {
			return true
		}

		// We only need to check each shared vertex once, so we only
		// consider the case where l.aVertex(l.aj+1) == l.b.Vertex(bj+1).
		if l.a.Vertex(l.aj+1) == l.b.Vertex(bj+1) {
			if l.swapped {
				if l.relation.wedgesCross(l.b.Vertex(bj), l.b.Vertex(bj+1), l.b.Vertex(bj+2), l.a.Vertex(l.aj), l.a.Vertex(l.aj+2)) {
					return true
				}
			} else {
				if l.relation.wedgesCross(l.a.Vertex(l.aj), l.a.Vertex(l.aj+1), l.a.Vertex(l.aj+2), l.b.Vertex(bj), l.b.Vertex(bj+2)) {
					return true
				}
			}
		}
	}

	return false
}
464843
func newEdge(src node, dest node) *edgeImpl {
	e := &edgeImpl{
		s:         src,
		d:         dest,
		notMarked: false,
	}
	src.addOut(e)
	dest.addIn(e)
	return e
}
297022
func ClipEdge(a, b r2.Point, clip r2.Rect) (aClip, bClip r2.Point, intersects bool) {
	// Compute the bounding rectangle of AB, clip it, and then extract the new
	// endpoints from the clipped bound.
	bound := r2.RectFromPoints(a, b)
	if bound, intersects = clipEdgeBound(a, b, clip, bound); !intersects {
		return aClip, bClip, false
	}
	ai := 0
	if a.X > b.X {
		ai = 1
	}
	aj := 0
	if a.Y > b.Y {
		aj = 1
	}

	return bound.VertexIJ(ai, aj), bound.VertexIJ(1-ai, 1-aj), true
}
1185011
func (p *Polygon) compareBoundary(o *Loop) int {
	result := -1
	for i := 0; i < len(p.loops) && result != 0; i++ {
		// If B crosses any loop of A, the result is 0. Otherwise the result
		// changes sign each time B is contained by a loop of A.
		result *= -p.loops[i].compareBoundary(o)
	}
	return result
}
155563
func (g *Graph) EdgesTo(v Vertex) []Edge {
	var result []Edge
	search := hashcode(v)
	for _, e := range g.Edges() {
		if hashcode(e.Target()) == search {
			result = append(result, e)
		}
	}

	return result
}
523888
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)
}
972702
func EdgesOfKind(kinds ...string) EdgeFunc {
	if len(kinds) == 0 {
		return func(g Interface, from, to graph.Node, edgeKinds sets.String) bool {
			return true
		}
	}

	allowedKinds := sets.NewString(kinds...)
	return func(g Interface, from, to graph.Node, edgeKinds sets.String) bool {
		return allowedKinds.HasAny(edgeKinds.List()...)
	}
}
1206916
func (c Cap) ContainsCell(cell Cell) bool {
	// If the cap does not contain all cell vertices, return false.
	var vertices [4]Point
	for k := 0; k < 4; k++ {
		vertices[k] = cell.Vertex(k)
		if !c.ContainsPoint(vertices[k]) {
			return false
		}
	}
	// Otherwise, return true if the complement of the cap does not intersect the cell.
	return !c.Complement().intersects(cell, vertices)
}
1144045
func edgeIntersectsRect(a, b r2.Point, r r2.Rect) bool {
	// First check whether the bounds of a Rect around AB intersects the given rect.
	if !r.Intersects(r2.RectFromPoints(a, b)) {
		return false
	}

	// Otherwise AB intersects the rect if and only if all four vertices of rect
	// do not lie on the same side of the extended line AB. We test this by finding
	// the two vertices of rect with minimum and maximum projections onto the normal
	// of AB, and computing their dot products with the edge normal.
	n := b.Sub(a).Ortho()

	i := 0
	if n.X >= 0 {
		i = 1
	}
	j := 0
	if n.Y >= 0 {
		j = 1
	}

	max := n.Dot(r.VertexIJ(i, j).Sub(a))
	min := n.Dot(r.VertexIJ(1-i, 1-j).Sub(a))

	return (max >= 0) && (min <= 0)
}
646602
func (c *CrossingEdgeQuery) candidates(a, b Point, shape Shape) []int {
	var edges []int

	// For small loops it is faster to use brute force. The threshold below was
	// determined using benchmarks.
	const maxBruteForceEdges = 27
	maxEdges := shape.NumEdges()
	if maxEdges <= maxBruteForceEdges {
		edges = make([]int, maxEdges)
		for i := 0; i < maxEdges; i++ {
			edges[i] = i
		}
		return edges
	}

	// Compute the set of index cells intersected by the query edge.
	c.getCellsForEdge(a, b)
	if len(c.cells) == 0 {
		return nil
	}

	// Gather all the edges that intersect those cells and sort them.
	// TODO(roberts): Shapes don't track their ID, so we need to range over
	// the index to find the ID manually.
	var shapeID int32
	for k, v := range c.index.shapes {
		if v == shape {
			shapeID = k
		}
	}

	for _, cell := range c.cells {
		if cell == nil {
		}
		clipped := cell.findByShapeID(shapeID)
		if clipped == nil {
			continue
		}
		for _, j := range clipped.edges {
			edges = append(edges, j)
		}
	}

	if len(c.cells) > 1 {
		edges = uniqueInts(edges)
	}

	return edges
}
898970
func Cross(a, b *T) T {
	return T{
		a[1]*b[0] - a[0]*b[1],
		a[0]*b[1] - a[1]*b[0],
	}
}
1212144
func (s *ShapeIndex) skipCellRange(begin, end CellID, t *tracker, disjointFromIndex bool) {
	// If we aren't in the interior of a shape, then skipping over cells is easy.
	if len(t.shapeIDs) == 0 {
		return
	}

	// Otherwise generate the list of cell ids that we need to visit, and create
	// an index entry for each one.
	skipped := CellUnionFromRange(begin, end)
	for _, cell := range skipped {
		var clippedEdges []*clippedEdge
		s.updateEdges(PaddedCellFromCellID(cell, cellPadding), clippedEdges, t, disjointFromIndex)
	}
}
1290476
func newEdges(n int, e EdgeSet) *Virtual {
	switch {
	case n < 0:
		return nil
	case n == 0:
		return null
	case n == 1:
		return singleton()
	}

	var noCost bool
	if e.Cost == nil {
		noCost = true
		e.Cost = zero
	}
	var noFilter bool
	if e.Keep == nil {
		noFilter = true
		e.Keep = alwaysEdge
	}

	from := e.From.And(Range(0, n))
	to := e.To.And(Range(0, n))
	if from.size() == 0 || to.size() == 0 {
		return Empty(n)
	}
	res := generic(n, e.Cost, func(v, w int) (edge bool) {
		return e.Contains(v, w)
	})

	intersect := from.And(to)
	union := from.Or(to)
	if noFilter {
		res.degree = func(v int) (deg int) {
			switch {
			case intersect.Contains(v):
				return union.size() - 1
			case from.Contains(v):
				return to.size()
			case to.Contains(v):
				return from.size()
			default:
				return
			}
		}
	}

	visit := func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
		switch {
		case intersect.Contains(v):
			for _, in := range union.And(Range(a, n)).set {
				for w := in.a; w < in.b; w++ {
					if v != w && e.Keep(v, w) && do(w, e.Cost(v, w)) {
						return true
					}
				}
			}
			return
		case from.Contains(v):
			for _, in := range to.And(Range(a, n)).set {
				for w := in.a; w < in.b; w++ {
					if e.Keep(v, w) && do(w, e.Cost(v, w)) {
						return true
					}
				}
			}
			return
		case to.Contains(v):
			for _, in := range from.And(Range(a, n)).set {
				for w := in.a; w < in.b; w++ {
					if e.Keep(v, w) && do(w, e.Cost(v, w)) {
						return true
					}
				}
			}
			return
		default:
			return
		}
	}

	visit0 := func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
		switch {
		case intersect.Contains(v):
			for _, in := range union.And(Range(a, n)).set {
				for w := in.a; w < in.b; w++ {
					if v != w && e.Keep(v, w) && do(w, 0) {
						return true
					}
				}
			}
			return
		case from.Contains(v):
			for _, in := range to.And(Range(a, n)).set {
				for w := in.a; w < in.b; w++ {
					if e.Keep(v, w) && do(w, 0) {
						return true
					}
				}
			}
			return
		case to.Contains(v):
			for _, in := range from.And(Range(a, n)).set {
				for w := in.a; w < in.b; w++ {
					if e.Keep(v, w) && do(w, 0) {
						return true
					}
				}
			}
			return
		default:
			return
		}
	}

	if noCost {
		res.visit = visit0
	} else {
		res.visit = visit
	}
	return res
}
318116
func (c Cell) DistanceToCell(target Cell) s1.ChordAngle {
	// If the cells intersect, the distance is zero.  We use the (u,v) ranges
	// rather than CellID intersects so that cells that share a partial edge or
	// corner are considered to intersect.
	if c.face == target.face && c.uv.Intersects(target.uv) {
		return 0
	}

	// Otherwise, the minimum distance always occurs between a vertex of one
	// cell and an edge of the other cell (including the edge endpoints).  This
	// represents a total of 32 possible (vertex, edge) pairs.
	//
	// TODO(roberts): This could be optimized to be at least 5x faster by pruning
	// the set of possible closest vertex/edge pairs using the faces and (u,v)
	// ranges of both cells.
	var va, vb [4]Point
	for i := 0; i < 4; i++ {
		va[i] = c.Vertex(i)
		vb[i] = target.Vertex(i)
	}
	minDist := s1.InfChordAngle()
	for i := 0; i < 4; i++ {
		for j := 0; j < 4; j++ {
			minDist, _ = UpdateMinDistance(va[i], vb[j], vb[(j+1)&3], minDist)
			minDist, _ = UpdateMinDistance(vb[i], va[j], va[(j+1)&3], minDist)
		}
	}
	return minDist
}
615699
func LineIntersection(one, two Line) (Point, bool) {
	p := one.P1
	q := two.P1

	r := one.P2
	r.Subtract(p)
	s := two.P2
	s.Subtract(q)

	// t = (q − p) × s / (r × s)
	// u = (q − p) × r / (r × s)
	// So then we define
	// qmp = (q - p)
	// rcs = (r × s)
	// and we get simply:
	// t = qmp × s / rcs
	// u = qmp × r / rcs
	qmp := q
	qmp.Subtract(p)
	qmpcs := CrossProduct(qmp, s)
	qmpcr := CrossProduct(qmp, r)
	rcs := CrossProduct(r, s)

	t := qmpcs / rcs
	u := qmpcr / rcs
	// if rcs == 0 then it's either collinear or parallel. It'll be +/- inf, so it'll skip this statement and return at the end
	if t >= 0 && t <= 1 && u >= 0 && u <= 1 {
		// the two line segments meet at the point p + t r = q + u s.
		return Point{p.X + t*r.X, p.Y + t*r.Y}, true
	}

	return Point{}, false
}
1357919
func (cu *CellUnion) IntersectsCellID(id CellID) bool {
	// Find index of array item that occurs directly after our probe cell:
	i := sort.Search(len(*cu), func(i int) bool { return id < (*cu)[i] })

	if i != len(*cu) && (*cu)[i].RangeMin() <= id.RangeMax() {
		return true
	}
	return i != 0 && (*cu)[i-1].RangeMax() >= id.RangeMin()
}
993601
func (ci CellID) EdgeNeighbors() [4]CellID {
	level := ci.Level()
	size := sizeIJ(level)
	f, i, j, _ := ci.faceIJOrientation()
	return [4]CellID{
		cellIDFromFaceIJWrap(f, i, j-size).Parent(level),
		cellIDFromFaceIJWrap(f, i+size, j).Parent(level),
		cellIDFromFaceIJWrap(f, i, j+size).Parent(level),
		cellIDFromFaceIJWrap(f, i-size, j).Parent(level),
	}
}