算法:两条线段求交点

问题情景:

验证两条线段是否相交时,需求两条线段的交点

算法详解:

已知两个线段分别是(x1,y1)(x2,y2)以及(x3,y3)(x4,y4)。

设线段所在的直线方程为ax+by+c=0

a1=y2-y1, b1=-(x2-x1), c1=-a1*x1-b1*y1=-x1*y2+x2*y1;

a2=y4-y3, b2=-(x4-x3), c2=-a2*x3-b2*y3=-x3*y4+x4*y3;

d=a1*b2-a2*b1

1. 判断是否相切:a1/b1=a2/b2;

2. 判断是否共线:a1/a2=c1/c2;

3. 求取交点:((b1*c2-b2*c1)/d,(a2*c1-a1*c2)/d)

4. 若判断两线段是否相交,则需要判断交点是否在这两条线段上(方法不限)。

代码优化:

上面许多表达式都可以用以下叉乘公式来代替

func(a,b,c,d)  return a*d-b*c;

原文地址:https://www.cnblogs.com/fr-ruiyang/p/9506866.html