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?
Let's assume we're given two rays a and b with starting points (origin vectors) a.s, b.s, and direction vectors a.d, b.d.
The two lines intersect if there is an intersection point p like:
p = a.s + a.d * u
p = b.s + b.d * v
If this equation system has a solution for u >= 0 and v >= 0 (the positive direction is what makes them rays), the rays intersect.
For the x/y coordinates of the 2d vectors, this means:
p.x = a.s.x + a.d.x * u
p.y = a.s.y + a.d.y * u
p.x = a.s.x + b.d.x * v
p.y = b.s.y + b.d.y * v
Further steps:
as.x + ad.x * u = bs.x + bd.x * v
as.y + ad.y * u = bs.y + bd.y * v
Solving against v:
v := (as.x + ad.x * u - bs.x) / bd.x
Inserting and solving against u:
a.s.y + a.d.y * u = b.s.y + b.d.y * ((a.s.x + a.d.x * u - b.s.x) / bd.x)
u := (a.s.y * b.d.x + b.d.y * b.s.x - b.s.y * b.d.x - b.d.y * a.s.x ) / (a.d.x * b.d.y - a.d.y * b.d.x)
After replacing the respective terms with a cross product, this becomes:
u := (b.s × b.d + b.d × a.s.y) / (a.d × b.d)
Calculate u, then calculate v, if both are positive the rays intersect, else not.