Determining if two rays intersect

问题:

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?

回答1:

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:

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)

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

回答2:

I am sorry to 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

Five subtractions, six multiplications and two divisions.

If you only need to know if the rays intersect, the signs of u and v are 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).

回答3:

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
    }
}

回答4:

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 p₁ + a₁ * v₁ = p₂ + a₂ * v₂
(note that there are two unknowns, a₁ and a₂, and two equations, since the p's and v's are multi-dimensional)

Solve for a₁ and a₂ - if they are both non-negative, they intersect. If one is negative, they don't intersect.

回答5:

GeomAlgorithms.com has some pretty sweet algorithms dealing with lines in 3D... Generally speaking though, the probability of two lines intersecting in 3D space is really quite low.

In 2D, 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.

回答6:

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

It works out to be five multiplications, six subtractions, and one comparison.

回答7:

If the lines are of infinite length, then they will always intersect, unless they are parallel. To check if they are parallel, find the slope of each line and compare them. The slope will just be (y2-y1)/(x2-x1).