判断两条射线是否相交 [英] Determining if two rays intersect

问题描述

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

I have two rays on a 2D plane that extend to infinity, but both have a starting point. They are both described by a starting point and a vector in the direction of the ray extending to infinity. I want to find out if the two rays intersect, but I don't need to know where they intersect (it's part of a collision detection algorithm).

到目前为止，我所看到的所有内容都描述了找到两条线或线段的交点.有没有快速的算法来解决这个问题?

Everything I have looked at so far describes finding the intersection point of two lines or line segments. Is there a fast algorithm to solve this?

推荐答案

给定:两条射线 a，b，起点(原矢量)as，bs，方向矢量 ad，bd.

Given: two rays a, b with starting points (origin vectors) as, bs, and direction vectors ad, bd.

如果有交点p，两条线相交:

The two lines intersect if there is an intersection point p:

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

如果此方程组有 u>=0 和 v>=0 的解(正方向使它们成为射线)，则射线相交.

If this equation system has a solution for u>=0 and v>=0 (the positive direction is what makes them rays), the rays intersect.

对于二维向量的 x/y 坐标，这意味着:

For the x/y coordinates of the 2d vectors, this means:

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

对 u 进行插入和求解:

Inserting and solving against u:

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，如果两者都为正则射线相交，否则不相交.

Calculate u, then calculate v, if both are positive the rays intersect, else not.

这篇关于判断两条射线是否相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！