线段相交判断

本文记录判断线段是否相交的方法。

判断线段是否相交

判断线段是否共线

判断 AB 和 CD 向量叉乘是否为 0， 如果为 0 则平行，如果 AB 和 AC、 AD 叉乘也为 0 则共线。

随后查看线段是否重叠，分别查看 x, y 是否重叠即可判断。

在不共线情况下判断是否相交

此种情况下线段相交有两种情况

1. A,B 两点分别在线段 CD 两侧，同时 C, D 两点分别在 AB 线段两侧

$$ \begin{array}{c} (\vec{AC}\times\vec{AB})\cdot(\vec{AD}\times\vec{AB})<0 \ (\vec{CA}\times\vec{CD})\cdot(\vec{CB}\times\vec{CD})<0 \end{array} $$

1. 第二种情况下由于端点在线段上，所以有一个叉乘为0，因此：

$$ \begin{array}{c} (\overrightarrow{AC}\times\overrightarrow{AB})\cdot(\overrightarrow{AD}\times\overrightarrow{AB})=0 \(\overrightarrow{CA}\times\overrightarrow{CD})\cdot(\overrightarrow{CB}\times\overrightarrow{CD})=0 \end{array} $$

计算交点

假设交点为$P$,则有$P= A+ \overrightarrow {AB}* t$, $t\in 0, 1$且$P= C+ \overrightarrow {CD}* u$, $u\in 0, 1$ 即 $$ \begin{array}{c} A+ \overrightarrow {AB}* t= C+ \overrightarrow {CD}* u \ \overrightarrow {AB}* t= \overrightarrow {AC}+ \overrightarrow {CD}* u \end{array} $$ **由于向量自身的叉乘为0**，所以上式两边同时叉乘 $\overrightarrow {CD}$ 可得： $$ \vec{CD}\times\vec{AB}*t=\vec{CD}\times\vec{AC} $$ 变形可得： $$ t=\frac{\overrightarrow{CD}\times\overrightarrow{AC}}{\overrightarrow{CD}\times\overrightarrow{AB}},\:t\in0,1 $$ 同理，两边同时叉乘$\overrightarrow{AB}$可得：$-\overrightarrow{AB}\times\overrightarrow{CD}*u=\overrightarrow{AB}\times\overrightarrow{AC}$ ,所以： $$ u=\frac{\overrightarrow{AB}\times\overrightarrow{AC}}{\overrightarrow{CD}\times\overrightarrow{AB}},\:u\in0,1 $$

参考资料

• https://zhuanlan.zhihu.com/p/598112630

文章链接： https://cloud.tencent.com/developer/article/2442743