两条线段是否相交原理及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线段两侧；

图４：一点在线段上；

图５：一侧；

 

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

*@idea: 根据直线向量同直线端点同点形成的向量叉乘判断点在的直线的哪端（顺时或逆时），根据这个结果判断一条直线的两个点是否在一条直线两边，

*@paragma one :line one  two :line two

*@return : true :intersection ,false:not intersection

*@ zhaoCQ

*@ 2020.5.19 

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

 

 

struct Line_Section

{

Point start;

Point end;

};

 

bool Line_intersection2(const Line_Section &l1, const Line_Section &l2)

{

//<快速排斥

if ((l1.start.x > l1.end.x ? l1.start.x : l1.end.x) < (l2.start.x < l2.end.x ? l2.start.x : l2.end.x) ||

(l1.start.y > l1.end.y ? l1.start.y : l1.end.y) < (l2.start.y < l2.end.y ? l2.start.y : l2.end.y) ||

(l2.start.x > l2.end.x ? l2.start.x : l2.end.x) < (l1.start.x < l1.end.x ? l1.start.x : l1.end.x) ||

(l2.start.y > l2.end.y ? l2.start.y : l2.end.y) < (l1.start.y < l1.end.y ? l1.start.y : l1.end.y))

{

return false;

}

 

//<vector  cross multi  

Point A=l2.start;

Point B=l2.end;

Point P=l1.start;

Point Q=l1.end;

 

int cross_AB_AP=(B.x-A.x)*(P.y-A.y)-(B.y-A.y)*(P.x-A.x); //< AB cross multi AP

int cross_AB_AQ=(B.x-A.x)*(Q.y-A.y)-(B.y-A.y)*(Q.x-A.x); //<AB cross multi AQ

//judge P,Q is same side of line AB ///int is out the range ,it can change the sign !!!!!!!!!

bool bSamesidePQ=(float)cross_AB_AP*cross_AB_AQ>0;

 

Point C=l1.start;

Point D=l1.end;

Point U=l2.start;

Point V=l2.end; 

 

int cross_CD_CU=(D.x-C.x)*(U.y-C.y)-(D.y-C.y)*(U.x-C.x); //< CD cross multi CU

int cross_CD_CV=(D.x-C.x)*(V.y-C.y)-(D.y-C.y)*(V.x-C.x); //< CD cross multi CV

//judge P,Q is same side of line AB ///int is out the range ,it can change the sign !!!!!!!!!

bool bSamesideUV=(float)cross_CD_CU*cross_CD_CV>0;   //<cast data type to avoid out of range 

 

//cross judge

if ( bSamesidePQ ||bSamesideUV)

{

return false;

}

   

return true;

}