线段相交

计算几何

说明

先做外接矩形筛选，再用叉积判断两端是否跨过另一线段。

分析

先比较两条线段的外接矩形，若矩形不相交即可立刻排除。随后用叉积判断每条线段的两个端点是否位于另一线段的两侧或边界上。

图解推演

正文两条对角线 (0,0)→(2,2) 与 (0,2)→(2,0) 的包围盒重叠，且各线段的端点分处另一条直线两侧，因此相交。仅叉积为零不能判相交：同一直线上相隔很远的两段仍不相交，需要包围盒或在线段范围内的判断。

查看图表代码

适用前提与边界

示例把端点接触和共线重叠都视为相交。

示例输入与调用

fmt.Println(Intersects(Point{0, 0}, Point{2, 2}, Point{0, 2}, Point{2, 0}))

运行输出

true

完整 Go 示例

package main

import "fmt"

type Point struct{ X, Y int }

func cross(a, b, c Point) int {
	return (b.X-a.X)*(c.Y-a.Y) - (b.Y-a.Y)*(c.X-a.X)
}
func Intersects(a, b, c, d Point) bool {
	if max(min(a.X, b.X), min(c.X, d.X)) > min(max(a.X, b.X), max(c.X, d.X)) || max(min(a.Y, b.Y), min(c.Y, d.Y)) > min(max(a.Y, b.Y), max(c.Y, d.Y)) {
		return false
	}
	return cross(a, b, c)*cross(a, b, d) <= 0 && cross(c, d, a)*cross(c, d, b) <= 0
}

func main() {
	fmt.Println(Intersects(Point{0, 0}, Point{2, 2}, Point{0, 2}, Point{2, 0}))
}