碰撞检测：判断线段相交

本文主要是介绍碰撞检测：判断线段相交，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文乃Siliphen原创，转载请注明出处：http://blog.csdn.net/stevenkylelee

文本demo演示：

在这里插入图片描述

本文介绍的判断线段相交的算法用到2D向量叉乘，
所以先来了解一下：2D向量的叉乘（叉积）

2D叉乘

3D 叉乘：
3D 叉乘的结果是一个 3D 向量，这个向量垂直于参与运算的2个向量的法向量。
3D 叉乘计算公式：（ a.y * b.z - b.y * a.z , a.z * b.x - b.z * a.x , a.x * b.y - b.x * a.y ）

2D叉乘：
2D 叉乘的结果是一个标量。
2D 叉乘就是把 2D 点看作 3D 的点（ z 轴的值为 0 ），套进 3D 叉乘公式进行计算。
例如：有2个2D向量 a , b ，计算叉乘就是：
（ a.y * b.z - b.y * 0 , 0 * b.x - b.z * a.x , a.x * b.y - b.x * a.y ）= ( 0 , 0 , a.x * b.y - b.x * a.y )
套进3D叉乘公式计算的2D叉乘的结果的 x , y 分量均为 0 ，只有 z 有意义。
所以，标量 z 是 2D 叉乘的结果。

2D 叉乘公式：
设两个 2D 向量 a , b，叉乘公式：a.x * b.y - b.x * a.y

向量 a 叉乘向量 b 结果的意义：

a ，b 向量构成的平行四边形的面积。
方位：以 a 为参考轴，b 相对于 a 的方位。
结果 > 0 正数：b 在 a 的左边，a 的逆时针旋转方向。a 逆时针旋转到 b 的角度小于180°。
结果 < 0 负数：b 在 a 的右边，a 的顺时针旋转方向。a 顺时针旋转到 b 的角度小于180°。
结果 = 0 ：a 和 b 向量是平行的。

在这里插入图片描述

如上图所示：
向量 a 把空间分为2部分：

左边的空间：逆时针旋转180°范围内的空间。
右边的空间：顺时针旋转180°范围内的空间。

a 叉乘 b 的结果是 > 0 的正数，b 在 a 的左边。
a 叉乘 c , d 的结果是 < 0 的负数，c , d 在 a 的右边。
a 叉乘 a 的结果是0。因为 a 和它自己是平行的。

2D向量叉乘demo演示：在这里插入图片描述

判断线段是否相交：基于2D叉乘

基本思想：

一个线段会把空间分为2部分，以这个线段为分界线，判断是否另一个线段2个端点分别在这个线段分割的2个空间中。
如果2个线段的2个端点都分别在另一个线段分割的2个空间中，那么就认为是相交。

如下图，有线段 a 和 b
在这里插入图片描述

线段 a 把空间分为2部分，浅蓝和浅绿2部分。
b 的2个端点 bp1、bp2 分别在 a 划分出来的2个空间中。
在这里插入图片描述

同样的，线段 b 把空间分为2部分，浅蓝和浅绿2部分。
a 的 2个端点 ap1 , ap2 分别在 b 划分出来的2个空间中。
在这里插入图片描述

如上图所示，
2个线段的2个端点都在另一个线段分割出来的2个空间中，这2个线段相交。

算法描述：

设有2个线段 a , b 。线段 a 的2个端点为：ap1 , ap2 , 线段 b 的 2个端点为：bp1 , bp2 。
条件1：是否向量 ap1->bp1 、ap1->bp2 分别位于向量 ap1->ap2 的左右2端。
条件2：是否向量 bp1->ap1 、bp1->ap2 分别位于向量 bp1->bp2 的左右2端。
当条件1和条件2同时满足时，线段 a , b 相交。

判断一个向量之于另一个向量的方位，可以用2D叉乘。

下图演示如何判断线段 a 的2个端点分别在线段 b 分割出来的2个空间中。
在这里插入图片描述

以 bp2 为起点，拉出3条向量。分别是 v = bp2->bp1 ，v1 = bp2->ap1 ， v2 = bp2->ap2
计算：
c1 = v 叉乘 v1
c2 = v 叉乘 v2
如果 c1 , c2 有一个为负数另一个为正数或者为0，那么说明线段a的2端分别在线段b分割的2个空间中。
c1 和 c2 的值相乘，结果为负数说明互为相反符号的数，否者是相同符号。
条件1计算完毕。

条件2的计算示意图如下，计算过程如法炮制条件1。
在这里插入图片描述