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 (its part of a collision detection algorithm).
Everything i have looked at so far describes finding the intersection point of two lines or line segments. Anyone know a fast algorithm to solve this?
If the lines are of infinite length, then they will Always intersect, unless they are paralell. To check if they are paralell, find the slope each line and compare them. Slope will just be (y2-y1)/(x2-x1).
This site has some pretty sweet algorithms dealing with lines in 3-d... generally speaking though, the probability of two lines intersecting in 3-d space is really quite low.
In 2-D, you have to check the slope. If the slope is not equal then they intersect. If the slope is equal, they intersect if a point on them has the same x-coordinate or the same y-coordinate.
I'm not going to real code here - the abstractions are exercises for the reader (or hopefully you're using a library that already has them)
boolean doTheyIntersect(Ray a, Ray b) {
Line aLine = MagicLibrary.createLineFromRay(a);
Line bLine = MagicLibrary.createLineFromRay(b);
Point intersection = MagicLibrary.intersectionPoint(aLine,bLine);
boolean aIntersect = MagicLibrary.rayIntersectsPoint(a,intersection);
boolean bIntersect = MagicLibrary.rayIntersectsPoint(b,intersection);
return aIntersect && bIntersect;
}
Given: two rays a, b with starting points (origin vectors) as, bs, and direction vectors ad, bd.
The two lines intersect if there is an intersection point p:
p = as + ad * u
p = bs + bd * 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 = 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
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:
u := (bs.y + bd.y * v - as.y) / ad.y
u := (bs.y + bd.y * (as.x + ad.x * u - bs.x) / bd.x - as.y) / ad.y
Calculate u, then calculate v, if both are positive the rays intersect, else not.
A ray can be represented by the set of points A + Vt, where A is the starting point, V is a vector indicating the direction of the ray, and t >= 0 is the parameter. Thus, to determine if two rays intersect, do this:
bool DoRaysIntersect(Ray r1, Ray r2)
{
// Solve the following equations for t1 and t2:
// r1.A.x + r1.V.x * t1 == r2.A.x + r2.V.x * t2
// r1.A.y + r1.V.y * t1 == r2.A.y + r2.V.y * t2
if(no solution) // (e.g. parallel lines)
{
if(r1 == r2) // same ray?
return true;
else
return false; // parallel, non-intersecting
}
else // unique solution
{
if(t1 >= 0 && t2 >= 0)
return true;
else
return false; // they would intersect if they are lines, but they are not lines
}
}
Lines are represented by a point p and a vector v:
line = p + a * v (for all a)
Rays are (the positive) half of that line:
ray = p + a * v (for all a >= 0)
To determine if two lines intersect, set them equal and solve:
intersection occurs where p1 + a1 * v1 = p2 + a2 * v2
(note that there are two unknowns, a1 and a2, and two equations, since the p's and v's are multi-dimensional)
Solve for a1 and a2 - if they are both non-negative, they intersect. If one is negative, they don't intersect.
I think I've figured out the answer to my question. Please take a look to see if it makes any sense (because it dosent really make any sense to me even though i figured it out, i suck at math).
I want only to check if the two rays intersect. I will go about it by calculating the direction of rotation of two "triangles" created from the two rays. They aren't really triangles but from a mathematical standpoint, if i only wanted to calculate the rotation of the triangle, i only need two vectors with a common starting point and the rest doesn't matter.
The first triangle will be formed by two vectors and a starting point. The starting point will be the first ray's starting point. The first vector will be the first ray's direction vector. The second vector will be the vector form the first ray's starting point to the second ray's starting point. From here we take the cross product of the two vectors and note the sign.
We do this again for the second triangle. Again, the starting point is the second ray's starting point. The first vector is the second ray's direction and the second vector is from the second ray's starting point to the first ray's starting point. We take the cross product again of the vectors and note the sign.
Now we simply take the two signs and check if they are the same. If they are the same, we have no intersection. If they are different we have an intersection. That's it!
Here's some psudo code:
sign1 = cross(vector1, point1 - point2)
sign2 = cross(vector2, point2 - point1)
if (sign1 * sign2 < 0) // if signs are mismatched, they will multiply to be negative
return intersection
works out to be 5 multiplications, 6 subtractions, and 1 comparison
I am sorry do disagree with the answer of Peter Walser. Solving the equations gives on my desk:
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)
Factoring out the common terms, this comes to:
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
5 subtractions, 6 multiplications and 2 divisions
If you only need to know if the rays intersect, the sign of u and v is enough, and these two divisons can be replaced by num*denom<0 or (sign(num) != sign(denom)), depending on what is more efficient on your target machine. Please note that the rare case of det==0 means that the rays do not intersect (one additional comparison).