确定两条光线是否相交

Question

我在2D平面上有两条光线延伸到无限远,但两者都有一个起点.它们都由起点和矢量在射线方向上描述,该射线延伸到无穷远.我想知道两条光线是否相交,但我不需要知道它们相交的位置(它是碰撞检测算法的一部分).

到目前为止,我所看到的一切都描述了找到两条线或线段的交点.是否有快速算法来解决这个问题？

Answer 1

我很遗憾不同意Peter Walser的回答.解决方程在我的桌子上给出:

u = ((bs.y - as.y) * bd.x - (bs.x - as.x) * bd.y) / (bd.x * ad.y - bd.y * ad.x)
v = ((bs.y - as.y) * ad.x - (bs.x - as.x) * ad.y) / (bd.x * ad.y - bd.y * ad.x)

考虑到常用术语,这就涉及到:

dx = bs.x - as.x
dy = bs.y - as.y
det = bd.x * ad.y - bd.y * ad.x
u = (dy * bd.x - dx * bd.y) / det
v = (dy * ad.x - dx * ad.y) / det

五次减法,六次乘法和两次除法.

如果您只需要知道光线是否相交,那么u和v的符号就足够了,这两个除数可以用num*denom <0或(sign(num)!= sign(denom))代替,具体取决于什么在目标计算机上更有效.

请注意,det == 0的罕见情况意味着光线不相交(另外一个比较).

Answer 2

给定:两条光线a,b具有起点(原点矢量)as,bs和方向矢量ad,bd.

如果存在交点p,则两条线相交:

p = as + ad * u
p = bs + bd * v

如果这个方程系统有一个u> = 0且v> = 0的解(正方向是它们射线的方向),则光线相交.

对于2d向量的x/y坐标,这意味着:

p.x = as.x + ad.x * u
p.y = as.y + ad.y * u
p.x = bs.x + bd.x * v
p.y = bs.y + bd.y * v

进一步的步骤

as.x + ad.x * u = bs.x + bd.x * v
as.y + ad.y * u = bs.y + bd.y * v

解决v:

v := (as.x + ad.x * u - bs.x) / bd.x

插入和解决你:

as.y + ad.y * u = bs.y + bd.y * ((as.x + ad.x * u - bs.x) / bd.x) 
u := (as.y*bd.x + bd.y*bs.x - bs.y*bd.x - bd.y*as.x ) / (ad.x*bd.y - ad.y*bd.x)

计算u,然后计算v,如果两者都是正数,则光线相交,否则不计算.