两条线段是否相交原理及C++实现

step 1: 快速排斥 

如上图1,2所示：

AB的最大X坐标，如果小于PQ的最小X坐标，则不相交

CD和UV判断同理，换成Ｙ坐标即可；　

step 2: 利用向量叉乘判断（亦称跨立方法）

 
 
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 )
 

如3,4,5所示，两个向量的计算结果符号分别对应相应的情况：

图３：Ｐ,Q分别在AB线段两侧；

图４：一点在线段上；

图５：一侧；

/********************

*