平面上两线段关系：相交、重叠

一、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']. \]