3.6 用矢量的叉积判断直线段是否有交
矢量叉积计算的另一个常用用途是直线段求交。求交算 法是计算机图形学的核心算法，也是体现速度和稳定性的重要标志，高效并且稳定的求交算法是任何 一个CAD软件都必需要重点关注的。求交包含两层概念，一个是判断是否相交，另一个是求出交点。直 线（段）的求交算法相对来说是比较简单的，首先来看看如何判断两直线段是否相交。
常规的 代数计算通常分三步，首先根据线段还原出两条线段所在直线的方程，然后联立方程组求出交点，最 后再判断交点是否在线段区间上。常规的代数方法非常繁琐，每次都要解方程组求交点，特别是交点 不在线段区间的情况，计算交点就是做无用功。计算几何方法判断直线段是否有交点通常分两个步骤 完成，这两个步骤分别是快速排斥试验和跨立试验。假设要判断线段P1P2和线段Q1Q2是否有交点，则 ：
（1） 快速排斥试验
设以线段 P1P2 为对角 线的矩形为R1， 设以线段 Q1Q2 为对角线的矩形为R2，如果R1和R2不相交，则两线段不会有交点；
（2）跨立试验。
如果两线段相交，则两线段必然相互跨立对 方，所谓跨立，指的是一条线段的两端点分别位于另一线段所在直线的两边。判断是否跨立，还是要 用到矢量叉积的几何意义。以图3为例，若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于 矢量( Q2 - Q1 ) 的两侧，即：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0
上式可改写成：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明线段P1P2和Q1Q2共线（但是不一定有 交点）。同理判断Q1Q2跨立P1P2的依据是：
( Q1 - P1 ) × ( P2 - P1 ) * ( Q2 - P1 ) × ( P2 - P1 ) < 0
具体情况如下图所示：
图3 直线段跨立试验示意图