// IntersectLine calculates the intersection of a rectangle and a line segment.
// (https://wiki.libsdl.org/SDL_IntersectRectAndLine)
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
}
322202
func (p *Path) IntersectionPath(path *Path) ([]*Point, [][2]int) {
	// TODO: done some sort of line sweep here if p.Length() is big enough
	var points []*Point
	var indexes [][2]int

	for i := 0; i < len(p.PointSet)-1; i++ {
		pLine := NewLine(&p.PointSet[i], &p.PointSet[i+1])

		for j := 0; j < len(path.PointSet)-1; j++ {
			pathLine := NewLine(&path.PointSet[j], &path.PointSet[j+1])

			if point := pLine.Intersection(pathLine); point != nil {
				points = append(points, point)
				indexes = append(indexes, [2]int{i, j})
			}
		}
	}

	return points, indexes
}
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
}
1344767
func (v *View) breakLine(x, y int) error {
	v.tainted = true

	x, y, err := v.realPosition(x, y)
	if err != nil {
		return err
	}

	if y < 0 || y >= len(v.lines) {
		return errors.New("invalid point")
	}

	var left, right []cell
	if x < len(v.lines[y]) { // break line
		left = make([]cell, len(v.lines[y][:x]))
		copy(left, v.lines[y][:x])
		right = make([]cell, len(v.lines[y][x:]))
		copy(right, v.lines[y][x:])
	} else { // new empty line
		left = v.lines[y]
	}

	lines := make([][]cell, len(v.lines)+1)
	lines[y] = left
	lines[y+1] = right
	copy(lines, v.lines[:y])
	copy(lines[y+2:], v.lines[y+1:])
	v.lines = lines
	return nil
}
1249961
func (c *CheckRunAnnotation) GetEndLine() int {
	if c == nil || c.EndLine == nil {
		return 0
	}
	return *c.EndLine
}
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
}
1206111
func (p *Path) IntersectionLine(line *Line) ([]*Point, [][2]int) {
	var points []*Point
	var indexes [][2]int

	for i := 0; i < len(p.PointSet)-1; i++ {
		pTest := NewLine(&p.PointSet[i], &p.PointSet[i+1])
		if point := pTest.Intersection(line); point != nil {
			points = append(points, point)
			indexes = append(indexes, [2]int{i, 0})
		}
	}

	return points, indexes
}
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)
}
1107
func (e editSet) intersect(x editSet) {
	for pos := range e {
		if _, ok := x[pos]; !ok {
			delete(e, pos)
		}
	}
}
428999
func (b *Bitmap) Intersect(other *Bitmap) *Bitmap {
	output := NewBitmap()
	iiter, _ := b.Containers.Iterator(0)
	jiter, _ := other.Containers.Iterator(0)
	i, j := iiter.Next(), jiter.Next()
	ki, ci := iiter.Value()
	kj, cj := jiter.Value()
	for i && j {
		if ki < kj {
			i = iiter.Next()
			ki, ci = iiter.Value()
		} else if ki > kj {
			j = jiter.Next()
			kj, cj = jiter.Value()
		} else { // ki == kj
			output.Containers.Put(ki, intersect(ci, cj))
			i, j = iiter.Next(), jiter.Next()
			ki, ci = iiter.Value()
			kj, cj = jiter.Value()
		}
	}
	return output
}
206851
func (ci CellID) Intersects(oci CellID) bool {
	return uint64(oci.RangeMin()) <= uint64(ci.RangeMax()) && uint64(oci.RangeMax()) >= uint64(ci.RangeMin())
}
571794
func Intersect(its ...Postings) Postings {
	if len(its) == 0 {
		return EmptyPostings()
	}
	if len(its) == 1 {
		return its[0]
	}

	l := len(its) / 2
	a := Intersect(its[:l]...)
	b := Intersect(its[l:]...)

	if a == EmptyPostings() || b == EmptyPostings() {
		return EmptyPostings()
	}
	return newIntersectPostings(a, b)
}
848842
func intersect(box orb.Bound, edge int, a, b orb.Point) orb.Point {
	if edge&8 != 0 {
		// top
		return orb.Point{a[0] + (b[0]-a[0])*(box.Max[1]-a[1])/(b[1]-a[1]), box.Max[1]}
	} else if edge&4 != 0 {
		// bottom
		return orb.Point{a[0] + (b[0]-a[0])*(box.Min[1]-a[1])/(b[1]-a[1]), box.Min[1]}
	} else if edge&2 != 0 {
		// right
		return orb.Point{box.Max[0], a[1] + (b[1]-a[1])*(box.Max[0]-a[0])/(b[0]-a[0])}
	} else if edge&1 != 0 {
		// left
		return orb.Point{box.Min[0], a[1] + (b[1]-a[1])*(box.Min[0]-a[0])/(b[0]-a[0])}
	}

	panic("no edge??")
}
353687
func (s1 Byte) Intersection(s2 Byte) Byte {
	var walk, other Byte
	result := NewByte()
	if s1.Len() < s2.Len() {
		walk = s1
		other = s2
	} else {
		walk = s2
		other = s1
	}
	for key := range walk {
		if other.Has(key) {
			result.Insert(key)
		}
	}
	return result
}
616699
func (term Range) Intersection(other Range) (intersect Range) {
	// If either range is empty then the intersection is empty
	if term.IsEmpty() || other.IsEmpty() {
		intersect = Empty()
		return
	}

	if other.Start.Within(term) {
		intersect.Start = other.Start
	} else if term.Start.Within(other) {
		intersect.Start = term.Start
	} else if term.Start.IsZero() && other.Start.IsZero() {
		// Unbounded
	} else {
		intersect = Empty()
		return
	}

	if other.End.Within(term) {
		intersect.End = other.End
	} else if term.End.Within(other) {
		intersect.End = term.End
	} else if term.End.IsZero() && other.End.IsZero() {
		// Unbounded
	} else {
		intersect = Empty()
		return
	}
	return
}
437102
func intersectBitmapRun(a, b *Container) *Container {
	statsHit("intersect/BitmapRun")
	var output *Container
	runs := b.runs()
	if b.n <= ArrayMaxSize || a.n <= ArrayMaxSize {
		// output is array container
		array := make([]uint16, 0, b.n)
		for _, iv := range runs {
			for i := iv.start; i <= iv.last; i++ {
				if a.bitmapContains(i) {
					array = append(array, i)
				}
				// If the run ends the container, break to avoid an infinite loop.
				if i == 65535 {
					break
				}
			}
		}

		output = NewContainerArray(array)
	} else {
		// right now this iterates through the runs and sets integers in the
		// bitmap that are in the runs. alternately, we could zero out ranges in
		// the bitmap which are between runs.
		output = NewContainerBitmap(0, nil)
		bitmap := output.bitmap()
		aBitmap := a.bitmap()
		for j := 0; j < len(runs); j++ {
			vb := runs[j]
			i := vb.start >> 6 // index into a
			vastart := i << 6
			valast := vastart + 63
			for valast >= vb.start && vastart <= vb.last && i < bitmapN {
				if vastart >= vb.start && valast <= vb.last { // a within b
					bitmap[i] = aBitmap[i]
					output.n += int32(popcount(aBitmap[i]))
				} else if vb.start >= vastart && vb.last <= valast { // b within a
					var mask uint64 = ((1 << (vb.last - vb.start + 1)) - 1) << (vb.start - vastart)
					bits := aBitmap[i] & mask
					bitmap[i] |= bits
					output.n += int32(popcount(bits))
				} else if vastart < vb.start { // a overlaps front of b
					offset := 64 - (1 + valast - vb.start)
					bits := (aBitmap[i] >> offset) << offset
					bitmap[i] |= bits
					output.n += int32(popcount(bits))
				} else if vb.start < vastart { // b overlaps front of a
					offset := 64 - (1 + vb.last - vastart)
					bits := (aBitmap[i] << offset) >> offset
					bitmap[i] |= bits
					output.n += int32(popcount(bits))
				}
				// update loop vars
				i++
				vastart = i << 6
				valast = vastart + 63
			}
		}
	}
	return output
}
1058528
func (s1 Int32) Intersection(s2 Int32) Int32 {
	var walk, other Int32
	result := NewInt32()
	if s1.Len() < s2.Len() {
		walk = s1
		other = s2
	} else {
		walk = s2
		other = s1
	}
	for key := range walk {
		if other.Has(key) {
			result.Insert(key)
		}
	}
	return result
}