// IntersectsCell reports whether this Polyline intersects the given Cell.
501578
func (p *Polyline) IntersectsCell(cell Cell) bool {
	if len(*p) == 0 {
		return false
	}

	// We only need to check whether the cell contains vertex 0 for correctness,
	// but these tests are cheap compared to edge crossings so we might as well
	// check all the vertices.
	for _, v := range *p {
		if cell.ContainsPoint(v) {
			return true
		}
	}

	cellVertices := []Point{
		cell.Vertex(0),
		cell.Vertex(1),
		cell.Vertex(2),
		cell.Vertex(3),
	}

	for j := 0; j < 4; j++ {
		crosser := NewChainEdgeCrosser(cellVertices[j], cellVertices[(j+1)&3], (*p)[0])
		for i := 1; i < len(*p); i++ {
			if crosser.ChainCrossingSign((*p)[i]) != DoNotCross {
				// There is a proper crossing, or two vertices were the same.
				return true
			}
		}
	}
	return false
}
1316045
func (rc *runContainer16) intersectCardinality(b *runContainer16) int64 {
	answer := int64(0)

	a := rc
	numa := int64(len(a.iv))
	numb := int64(len(b.iv))
	if numa == 0 || numb == 0 {
		return 0
	}

	if numa == 1 && numb == 1 {
		if !haveOverlap16(a.iv[0], b.iv[0]) {
			return 0
		}
	}

	var acuri int64
	var bcuri int64

	astart := int64(a.iv[acuri].start)
	bstart := int64(b.iv[bcuri].start)

	var intersection interval16
	var leftoverstart int64
	var isOverlap, isLeftoverA, isLeftoverB bool
	var done bool
	pass := 0
toploop:
	for acuri < numa && bcuri < numb {
		pass++

		isOverlap, isLeftoverA, isLeftoverB, leftoverstart, intersection =
			intersectWithLeftover16(astart, int64(a.iv[acuri].last()), bstart, int64(b.iv[bcuri].last()))

		if !isOverlap {
			switch {
			case astart < bstart:
				acuri, done = a.findNextIntervalThatIntersectsStartingFrom(acuri+1, bstart)
				if done {
					break toploop
				}
				astart = int64(a.iv[acuri].start)

			case astart > bstart:
				bcuri, done = b.findNextIntervalThatIntersectsStartingFrom(bcuri+1, astart)
				if done {
					break toploop
				}
				bstart = int64(b.iv[bcuri].start)

				//default:
				//	panic("impossible that astart == bstart, since !isOverlap")
			}

		} else {
			// isOverlap
			answer += int64(intersection.last()) - int64(intersection.start) + 1
			switch {
			case isLeftoverA:
				// note that we change astart without advancing acuri,
				// since we need to capture any 2ndary intersections with a.iv[acuri]
				astart = leftoverstart
				bcuri++
				if bcuri >= numb {
					break toploop
				}
				bstart = int64(b.iv[bcuri].start)
			case isLeftoverB:
				// note that we change bstart without advancing bcuri,
				// since we need to capture any 2ndary intersections with b.iv[bcuri]
				bstart = leftoverstart
				acuri++
				if acuri >= numa {
					break toploop
				}
				astart = int64(a.iv[acuri].start)
			default:
				// neither had leftover, both completely consumed
				// optionally, assert for sanity:
				//if a.iv[acuri].endx != b.iv[bcuri].endx {
				//	panic("huh? should only be possible that endx agree now!")
				//}

				// advance to next a interval
				acuri++
				if acuri >= numa {
					break toploop
				}
				astart = int64(a.iv[acuri].start)

				// advance to next b interval
				bcuri++
				if bcuri >= numb {
					break toploop
				}
				bstart = int64(b.iv[bcuri].start)
			}
		}
	} // end for toploop

	return answer
}
714783
func (m TerrainMap) Cell(c coord.Cell) TerrainType {
	x := c.X - m.Bounds.TopL.X
	y := -(c.Y - m.Bounds.TopL.Y)

	return m.TerrainTypes[y][x]
}
530711
func CellFromCellID(id CellID) Cell {
	c := Cell{}
	c.id = id
	f, i, j, o := c.id.faceIJOrientation()
	c.face = int8(f)
	c.level = int8(c.id.Level())
	c.orientation = int8(o)
	c.uv = ijLevelToBoundUV(i, j, int(c.level))
	return c
}
714313
func trimCell(column []xlsxC) []xlsxC {
	col := make([]xlsxC, len(column))
	i := 0
	for _, c := range column {
		if c.S != 0 || c.V != "" || c.F != nil || c.T != "" {
			col[i] = c
			i++
		}
	}
	return col[0:i]
}
49082
func (c Cap) IntersectsCell(cell Cell) bool {
	// If the cap contains any cell vertex, return true.
	var vertices [4]Point
	for k := 0; k < 4; k++ {
		vertices[k] = cell.Vertex(k)
		if c.ContainsPoint(vertices[k]) {
			return true
		}
	}
	return c.intersects(cell, vertices)
}
1320415
func (cu *CellUnion) Intersects(o CellUnion) bool {
	for _, c := range *cu {
		if o.IntersectsCellID(c) {
			return true
		}
	}

	return false
}
935931
func (l Line) IntersectRect(r Rect) Vec {
	// Check if either end of the line segment are within the rectangle
	if r.Contains(l.A) || r.Contains(l.B) {
		// Use the Rect.Intersect to get minimal return value
		rIntersect := l.Bounds().Intersect(r)
		if rIntersect.H() > rIntersect.W() {
			// Go vertical
			return V(0, rIntersect.H())
		}
		return V(rIntersect.W(), 0)
	}

	// Check if any of the rectangles' edges intersect with this line.
	for _, edge := range r.Edges() {
		if _, ok := l.Intersect(edge); ok {
			// Get the closest points on the line to each corner, where:
			//  - the point is contained by the rectangle
			//  - the point is not the corner itself
			corners := r.Vertices()
			closest := ZV
			closestCorner := corners[0]
			for _, c := range corners {
				cc := l.Closest(c)
				if closest == ZV || (closest.Len() > cc.Len() && r.Contains(cc)) {
					closest = cc
					closestCorner = c
				}
			}

			return closest.To(closestCorner)
		}
	}

	// No intersect
	return ZV
}
1246889
func (t *tracker) atCellID(cellid CellID) bool {
	return cellid.RangeMin() == t.nextCellID
}
925567
func (c Cap) intersects(cell Cell, vertices [4]Point) bool {
	// If the cap is a hemisphere or larger, the cell and the complement of the cap
	// are both convex. Therefore since no vertex of the cell is contained, no other
	// interior point of the cell is contained either.
	if c.radius >= s1.RightChordAngle {
		return false
	}

	// We need to check for empty caps due to the center check just below.
	if c.IsEmpty() {
		return false
	}

	// Optimization: return true if the cell contains the cap center. This allows half
	// of the edge checks below to be skipped.
	if cell.ContainsPoint(c.center) {
		return true
	}

	// At this point we know that the cell does not contain the cap center, and the cap
	// does not contain any cell vertex. The only way that they can intersect is if the
	// cap intersects the interior of some edge.
	sin2Angle := c.radius.Sin2()
	for k := 0; k < 4; k++ {
		edge := cell.Edge(k).Vector
		dot := c.center.Vector.Dot(edge)
		if dot > 0 {
			// The center is in the interior half-space defined by the edge. We do not need
			// to consider these edges, since if the cap intersects this edge then it also
			// intersects the edge on the opposite side of the cell, because the center is
			// not contained with the cell.
			continue
		}

		// The Norm2() factor is necessary because "edge" is not normalized.
		if dot*dot > sin2Angle*edge.Norm2() {
			return false
		}

		// Otherwise, the great circle containing this edge intersects the interior of the cap. We just
		// need to check whether the point of closest approach occurs between the two edge endpoints.
		dir := edge.Cross(c.center.Vector)
		if dir.Dot(vertices[k].Vector) < 0 && dir.Dot(vertices[(k+1)&3].Vector) > 0 {
			return true
		}
	}
	return false
}
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
}
1285404
func (c Cap) Intersects(other Cap) bool {
	if c.IsEmpty() || other.IsEmpty() {
		return false
	}

	return c.radius.Add(other.radius) >= ChordAngleBetweenPoints(c.center, other.center)
}
251203
func IntersectString(x []string, y []string) []string {
	if len(x) == 0 || len(y) == 0 {
		return []string{}
	}

	set := []string{}
	hash := map[string]struct{}{}

	for _, v := range x {
		hash[v] = struct{}{}
	}

	for _, v := range y {
		_, ok := hash[v]
		if ok {
			set = append(set, v)
		}
	}

	return set
}
102311
func (l *Line) Intersects(line *Line) bool {
	s1 := l.Side(&line.a)
	s2 := l.Side(&line.b)
	s3 := line.Side(&l.a)
	s4 := line.Side(&l.b)

	if s1 != s2 && s3 != s4 {
		return true
	}

	// Special Cases
	// l1 and l2.a collinear, check if l2.a is on l1
	lBound := l.Bound()
	if s1 == 0 && lBound.Contains(&line.a) {
		return true
	}

	// l1 and l2.b collinear, check if l2.b is on l1
	if s2 == 0 && lBound.Contains(&line.b) {
		return true
	}

	// TODO: are these next two tests redudant give the test above.
	// Thinking yes if there is round off magic.

	// l2 and l1.a collinear, check if l1.a is on l2
	lineBound := line.Bound()
	if s3 == 0 && lineBound.Contains(&l.a) {
		return true
	}

	// l2 and l1.b collinear, check if l1.b is on l2
	if s4 == 0 && lineBound.Contains(&l.b) {
		return true
	}

	return false
}
217987
func (l *loopCrosser) cellCrossesCell(aClipped, bClipped *clippedShape) bool {
	// Test all edges of aClipped against all edges of bClipped.
	for _, edge := range aClipped.edges {
		l.startEdge(edge)
		if l.edgeCrossesCell(bClipped) {
			return true
		}
	}

	return false
}
1052881
func (t Term) Intersects(args ...interface{}) Term {
	return constructMethodTerm(t, "Intersects", p.Term_INTERSECTS, args, map[string]interface{}{})
}
491558
func (a *Rect) IntersectLine(X1, Y1, X2, Y2 *int32) bool {
	if a.Empty() {
		return false
	}

	x1 := *X1
	y1 := *Y1
	x2 := *X2
	y2 := *Y2
	rectX1 := a.X
	rectY1 := a.Y
	rectX2 := a.X + a.W - 1
	rectY2 := a.Y + a.H - 1

	// Check if the line is entirely inside the rect
	if x1 >= rectX1 && x1 <= rectX2 && x2 >= rectX1 && x2 <= rectX2 &&
		y1 >= rectY1 && y1 <= rectY2 && y2 >= rectY1 && y2 <= rectY2 {
		return true
	}

	// Check if the line is entirely outside the rect
	if (x1 < rectX1 && x2 < rectX1) || (x1 > rectX2 && x2 > rectX2) ||
		(y1 < rectY1 && y2 < rectY1) || (y1 > rectY2 && y2 > rectY2) {
		return false
	}

	// Check if the line is horizontal
	if y1 == y2 {
		if x1 < rectX1 {
			*X1 = rectX1
		} else if x1 > rectX2 {
			*X1 = rectX2
		}
		if x2 < rectX1 {
			*X2 = rectX1
		} else if x2 > rectX2 {
			*X2 = rectX2
		}

		return true
	}

	// Check if the line is vertical
	if x1 == x2 {
		if y1 < rectY1 {
			*Y1 = rectY1
		} else if y1 > rectY2 {
			*Y1 = rectY2
		}
		if y2 < rectY1 {
			*Y2 = rectY1
		} else if y2 > rectY2 {
			*Y2 = rectY2
		}

		return true
	}

	// Use Cohen-Sutherland algorithm when all shortcuts fail
	outCode1 := computeOutCode(a, x1, y1)
	outCode2 := computeOutCode(a, x2, y2)
	for outCode1 != 0 || outCode2 != 0 {
		if outCode1&outCode2 != 0 {
			return false
		}

		if outCode1 != 0 {
			var x, y int32
			if outCode1&codeTop != 0 {
				y = rectY1
				x = x1 + ((x2-x1)*(y-y1))/(y2-y1)
			} else if outCode1&codeBottom != 0 {
				y = rectY2
				x = x1 + ((x2-x1)*(y-y1))/(y2-y1)
			} else if outCode1&codeLeft != 0 {
				x = rectX1
				y = y1 + ((y2-y1)*(x-x1))/(x2-x1)
			} else if outCode1&codeRight != 0 {
				x = rectX2
				y = y1 + ((y2-y1)*(x-x1))/(x2-x1)
			}

			x1 = x
			y1 = y
			outCode1 = computeOutCode(a, x, y)
		} else {
			var x, y int32
			if outCode2&codeTop != 0 {
				y = rectY1
				x = x1 + ((x2-x1)*(y-y1))/(y2-y1)
			} else if outCode2&codeBottom != 0 {
				y = rectY2
				x = x1 + ((x2-x1)*(y-y1))/(y2-y1)
			} else if outCode2&codeLeft != 0 {
				x = rectX1
				y = y1 + ((y2-y1)*(x-x1))/(x2-x1)
			} else if outCode2&codeRight != 0 {
				x = rectX2
				y = y1 + ((y2-y1)*(x-x1))/(x2-x1)
			}

			x2 = x
			y2 = y
			outCode2 = computeOutCode(a, x, y)
		}
	}

	*X1 = x1
	*Y1 = y1
	*X2 = x2
	*Y2 = y2

	return true
}