本文共 885 字，大约阅读时间需要 2 分钟。

判断两线段是否相交

已知两线段$a_1{a}_2$和$b_1{b}_2$，判断是否相交

代码模板

bool segment_intersection(Point a1,Point a2,Point b1,Point b2){
   	double c1 = cross(a2 - a1,b1 - a1), c2 = cross(a2 - a1,b2 - a1);	double c3 = cross(b2 - b1,a2 - b1), c4 = cross(b2 - b1,a1 - b1);	return (c1 * c2 <= 0 && c3 * c4 <= 0);}

证明

有两条线段$a_1{a}_2$和$b_1{b}_2$，我们只需先证明$a_1$和$a_2$分别在$b_1{b}_2$的两侧，然后证明$b_1$和$b_2$分别在$a_1{a}_2$，当两个同时满足时，两线段一定相交。

然后关键就是如何判断两点在线段两侧，如下图：

转载地址：http://nbbki.baihongyu.com/