平面上两线段关系：相交、重叠
一、Mathematica 代码
【判断相交或重叠+交点坐标或重叠线段】
定义函数：
(*定义函数*)
fp[p1_, p2_, p3_, p4_] := Block[{
d = Det[{p2 - p1, p3 - p4}],
a, b, aa,
p12 = p2 - p1, k = 1
},
If[d != 0,
a = Det[{p3 - p1, p3 - p4}]/d;
b = Det[{p2 - p1, p3 - p1}]/d;
If[0 <= a <= 1 && 0 <= b <= 1,
{"相交", p1 + p12 a},
{"不相交", p1 + p12 a}
]
,
If[Abs[p12[[1]]] > Abs[p12[[2]]], k = 1, k = 2];
aa = MinMax[{(p3 - p1)[[k]], (p4 - p1)[[k]]}/p12[[k]]];
If[aa[[1]] > 1 || aa[[2]] < 0,
{"不重叠", {}},
{"重叠", {p1 + p12 Max[{0, aa[[1]]}], p1 + p12 Min[{1, aa[[2]]}]}}
]
]
];测试两线段是否相交：
(*测试：相交*)
{p1, p2, p3, p4} = RandomReal[10, {4, 2}];
rs = fp[p1, p2, p3, p4]
(*绘图*)
Graphics[{
{Gray, Line[{p1, p2}], Line[{p3, p4}]},
{AbsolutePointSize[3], Black, Point[{p1, p2, p3, p4}]},
If[rs[[1]] == "相交", {AbsolutePointSize[5], Red, Point[rs[[2]]]}],
If[rs[[1]] == "不相交", {AbsolutePointSize[5], Gray, Point[rs[[2]]]}],
If[rs[[1]] == "重叠", {AbsoluteThickness[5], Red, Line[rs[[2]]]}]
}, ImageSize -> Medium, Frame -> True,
PlotRange -> {{0, 10}, {0, 10}}]测试两线段是否重叠：
(*测试：重叠*)
p1 = {0, 0};
p2 = {1, 0};
p3 = {-1, 0};
p4 = {0.5, 0};
rs = fp[p1, p2, p3, p4]
(*绘图*)
Graphics[{
{Gray, Line[{p1, p2}], Line[{p3, p4}]},
{AbsolutePointSize[3], Black, Point[{p1, p2, p3, p4}]},
If[rs[[1]] == "相交", {AbsolutePointSize[5], Red, Point[rs[[2]]]}],
If[rs[[1]] == "不相交", {AbsolutePointSize[5], Gray, Point[rs[[2]]]}],
If[rs[[1]] == "重叠", {AbsoluteThickness[5], Red, Line[rs[[2]]]}]
}, ImageSize -> Medium, Frame -> True,
PlotRange -> {{-2, 2}, Automatic}]二、公式解读
【定义】给定平面上两条线段 $\overrightarrow{P_1P_2}$ 与 $\overrightarrow{P_3P_4}$，线段的顶点坐标 $\mathbf{P_k}=(x_k,y_k)^T,\;k=1,2,3,4$。
$$ \overrightarrow{P_1P_2}:\mathbf{P_1}+(\mathbf{P_2}-\mathbf{P_1})\alpha,\;\alpha\in[0,1]\\ \overrightarrow{P_3P_4}:\mathbf{P_3}+(\mathbf{P_4}-\mathbf{P_3})\beta,\;\beta\in[0,1] $$
2.1 判断两线段是否相交
把两条线段放在三维空间的 XOY 平面，按以下公式计算两向量的叉积 $\overrightarrow{V_{12,13}}=\overrightarrow{P_1P_2}\times\overrightarrow{P_1P_3}$，叉积的结果是垂直于 XOY 平面的向量 $(0,0,z_{12,13})^T$。
$$ \overrightarrow{V_{12,13}}:=\overrightarrow{P_1P_2}\times\overrightarrow{P_1P_3}=\left|\begin{matrix} \mathrm{i} & \mathrm{j} & \mathrm{k}\\ x_2-x_1 & y_2-y_1 & 0\\ x_3-x_1 & y_3-y_1 & 0 \end{matrix}\right| = 0 \mathrm{i}+0\mathrm{j}+\left|\begin{matrix} x_2-x_1 & y_2-y_1\\ x_3-x_1 & y_3-y_1 \end{matrix}\right|\mathrm{k} $$
记
$$ z_{12,13}:=\left|\begin{matrix} x_2-x_1 & y_2-y_1\\ x_3-x_1 & y_3-y_1 \end{matrix}\right| $$
根据叉积的几何意义有：
- 当向量 $\overrightarrow{P_1P_2}$ 在 $180^\circ$ 内可逆时针旋转到向量 $\overrightarrow{P_1P_3}$ 时，它们的叉积在 $z$ 轴的分量 $z_{12,13}>0$；
- 当向量 $\overrightarrow{P_1P_2}$ 在 $180^\circ$ 内可顺时针旋转到向量 $\overrightarrow{P_1P_3}$ 时，它们的叉积在 $z$ 轴的分量 $z_{12,13}<0$；
- 当两向量共线时，它们叉积在 $z$ 轴的分量 $z_{12,13}=0$。
那么，当下面的行列式之积小于 0 时，点 $P_3,P_4$ 在直线 $P_1P_2$ 两侧；大于 0 时，点 $P_3,P_4$ 在直线 $P_1P_2$ 同侧；等于 0 时，点 $P_3,P_4$ 至少有一个在直线 $P_1P_2$ 上。
$$ \left|\begin{matrix} x_2-x_1 & y_2-y_1\\ {\color{blue}x_3}-x_1 & {\color{blue}y_3}-y_1 \end{matrix}\right| \times \left|\begin{matrix} x_2-x_1 & y_2-y_1\\ {\color{blue}x_4}-x_1 & {\color{blue}y_4}-y_1 \end{matrix}\right| $$
因此，当下面两个不等式都成立时，两线段相交。
$$ \begin{align} \begin{cases} \left| \begin{matrix} x_2 - x_1 & y_2 - y_1\\ {\color {blue}x_3} - x_1 & {\color{blue}y_3} - y_1 \end {matrix} \right | \times \left | \begin{matrix} x_2 - x_1 & y_2 - y_1\\ {\color {blue}x_4} - x_1 & {\color{blue}y_4} - y_1 \end{matrix} \right | < 0 \\ \\ \left | \begin{matrix} x_4 - x_3 & y_4 - y_3\\ {\color {blue}x_1} - x_3 & {\color{blue}y_1} - y_3 \end{matrix} \right | \times \left | \begin{matrix} x_4 - x_3 & y_4 - y_3\\ {\color {blue}x_2} - x_3 & {\color{blue}y_2} - y_3 \end{matrix} \right | < 0 \end{cases} \end{align} $$
当其中一个式子等于 0，另一个小于 0 时，其中一条线段的顶点在另一条线段内（不含顶点）。
当两个式子都等于 0 时，本方法失效，需要使用下面介绍的方法判断。
提示：由于只需要知道行列式乘积的符号即可，并不需要计算出行列式的具体值，因此在计算量上面是有很大优化空间的。例如，在计算 $ad-bc$ 的符号，可以先分别判断 a、b、c、d 的符号，就可以推出结果的符号了（当然这个方法很笨，肯定还有更优的方法，这里只做抛砖引玉）：
- a 和 d 同号，b 和 c 异号时，结果肯定>0
- a 和 d 异号，b 和 c 同号时，结果肯定<0
- 其他情况才需要先计算出行列式的值，再判断结果的符号。
2.2 计算两线段交点
$$ \begin{align} \mathbf{P_1}+(\mathbf{P_2}-\mathbf{P_1})\alpha&=\mathbf{P_3}+(\mathbf{P_4}-\mathbf{P_3})\beta\\ \alpha,\beta&\in[0,1] \end{align} $$
将上式改写成坐标形式：
$$ \begin{cases} (x_2-x_1)\alpha + (x_3-x_4)\beta=x_3-x_1\\ (y_2-y_1)\alpha + (y_3-y_4)\beta=y_3-y_1\\ \alpha\in[0,1]\\ \beta\in[0,1] \end{cases} $$
记
$$ d:=\left| \begin{matrix} x_2 - x_1 & x_3 - x_4 \\ y_2 - y_1 & y_3 - y_4 \end {matrix} \right | $$
1）当两线段不共线时 $d\neq0$，根据克莱姆法则可解出 $\alpha,\beta$：
$$ \alpha=\dfrac{ \left| \begin{matrix} x_3 - x_1 & x_3 - x_4 \\ y_3 - y_1 & y_3 - y_4 \end {matrix} \right | }{ d }, \; \beta=\dfrac{ \left| \begin{matrix} x_2 - x_1 & x_3 - x_1 \\ y_2 - y_1 & y_3 - y_1 \end {matrix} \right | }{ d } $$
如果 $\alpha,\beta\in[0,1]$，则交点坐标为 $\mathbf{P}=\mathbf{P_1}+(\mathbf{P_2}-\mathbf{P_1})\alpha=\mathbf{P_3}+(\mathbf{P_4}-\mathbf{P_3})\beta$；当 $\alpha,\beta$ 至少有一个不在区间 $[0,1]$ 内时，两线段不相交。
2）当两线段共线时 $d=0$，分别解出以下2个关于 $\alpha$ 方程，得到两个解 $\alpha_1,\alpha_2$，不妨假定：$\alpha_1\leqslant\alpha_2$。
$$ \begin{align} \mathbf{P_1}+(\mathbf{P_2}-\mathbf{P_1})\alpha=\mathbf{P_3}\\ \mathbf{P_1}+(\mathbf{P_2}-\mathbf{P_1})\alpha=\mathbf{P_4} \end{align} $$
当两区间 $[0,1]$ 与 $[\alpha_1,\alpha_2]$ 无重叠部分时，两线段也不重叠；当两区间有重叠部分时，记两区间重叠部分为 $[\alpha_1',\alpha_2']$，则两线段重叠部分为：
$$ \mathbf{P}=\mathbf{P_1}+(\mathbf{P_2}-\mathbf{P_1})\alpha,\;\alpha\in[\alpha_1',\alpha_2']. $$
