find线段交点的最佳方法

我需要find二维空间中两个线段之间的交点。 我用两条线的坐标来接收它们。 因为它们是线段,我还需要知道它们是否实际上相交在一起。

我可以find很多方法来做到这一点,但我想知道什么方法在GLSL中有最好的性能。

这个问题可能非常容易或者非常困难; 这取决于你的应用程序。 如果你想要的只是交点,下面的工作应该是:


令A,B,C,D为二维空间位置向量。 那么定向线段AB&CD由下式给出:

AB=A+r(BA), r in [0,1] CD=C+s(DC), s in [0,1] 

如果AB和CD相交,那么

 A+r(BA)=C+s(DC), or Ax+r(Bx-Ax)=Cx+s(Dx-Cx) Ay+r(By-Ay)=Cy+s(Dy-Cy) for some r,s in [0,1] 

解决上述的r和s产量

  (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy) r = ----------------------------- (eqn 1) (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx) (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay) s = ----------------------------- (eqn 2) (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx) 

设P是交点的位置vector

 P=A+r(BA) or Px=Ax+r(Bx-Ax) Py=Ay+r(By-Ay) 

通过检查r&s的值,你也可以确定一些其他的限制条件:

 If 0<=r<=1 & 0<=s<=1, intersection exists r<0 or r>1 or s<0 or s>1 line segments do not intersect If the denominator in eqn 1 is zero, AB & CD are parallel If the numerator in eqn 1 is also zero, AB & CD are collinear. 
  • 如果它们是共线的,则可以将这些分段投影到x轴或y轴,并且检查投影区间的重叠。
  • 如果需要两条线的交叉点(本文中的线意味着无限线),而不管两条线是否相交,则
  • 如果r> 1,P位于AB的扩展
  • 如果r <0,则P位于BA的扩展部分
  • 如果s> 1,P位于CD的扩展名上
  • 如果s <0,P位于DC的扩展

还要注意公式1和2的分母是相同的。


来源(复制粘贴): http : //www.gamers.org/dEngine/rsc/usenet/comp.graphics.algorithms.faq