Determining if two rays intersect

Question

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?

Solution 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.

Solution 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).

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

Solution 4

I found this post while trying to find the intersection point between two rays, based on other answers here. Just in case someone else has arrived here looking for the same answer, here's an answer in TypeScript / JavaScript.

/**
 * Get the intersection of two rays, with origin points p0 and p1, and direction vectors n0 and n1.
 * @param p0 The origin point of the first ray
 * @param n0 The direction vector of the first ray
 * @param p1 The origin point of the second ray
 * @param n1 The direction vector of the second ray
 * @returns
 */
export function getRaysIntersection(
  p0: number[],
  n0: number[],
  p1: number[],
  n1: number[]
): number[] | undefined {
  const dx = p1[0] - p0[0];
  const dy = p1[1] - p0[1];
  const det = n1[0] * n0[1] - n1[1] * n0[0];
  const u = (dy * n1[0] - dx * n1[1]) / det;
  const v = (dy * n0[0] - dx * n0[1]) / det;
  if (u < 0 || v < 0) return undefined; // Might intersect as lines, but as rays.

  const m0 = n0[1] / n0[0];
  const m1 = n1[1] / n1[0];
  const b0 = p0[1] - m0 * p0[0];
  const b1 = p1[1] - m1 * p1[0];
  const x = (b1 - b0) / (m0 - m1);
  const y = m0 * x + b0;

  return Number.isFinite(x) ? [x, y] : undefined;
}

Demo here: https://codesandbox.io/s/intersection-of-two-rays-mcwst

Solution 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.

View more solutions

Comments

[fbrereto]

2D or 3D? If the former simply check and see if the slope is the same for both: if so they are either parallel or the same line. Otherwise they will intersect.

[Carl Norum]

These are rays, not lines, then? All lines intersect in two dimensions, unless they're parallel.

[Faken]

@fbereto: sorry, 2D plane. Edited to reflect that.

[Faken]

@Carl Norum: Yea, your right. Sorry you're right

[BetweenTwoTests]

@floreto: except that, since they are half-lines, the intersection point need not lie on one of them. If it is 3D, it's better to think harder about what "intersects" means.

[Kurucu]

A ray implies they come from a common source, and therefore intersect at the source...?

[Faken]

@Kurucu: Two rays? Either way they are a line that goes in one direction only. Outwards from a starting point in the direction of a known vector. I have two pairs of starting point/vector combos.

[Kurucu]

Actually, having a rething, taking a different meaning to your question than the other answers so far: your lines have a known end, and the other 'end' goes off to infinity. Therefore, it could be that they are neither parallel nor intersect (if the 'intersection' point is behind one of the known line endings). I haven't posted an answer as I haven't got the time to solve it, but using the different gradients theories below are not sufficient. You probably need to solve for the intersection, then work out if that intersection corresponds to a positive quantity for the vectors for both lines.

[corsiKa]

@jpalecek Are they really half lines? Or simply not as infinite as real lines? :-)

[Faken]

@Kurucu: Yes! That is what i am asking. They can both neither be parallel and not intersect. I'm looking for a simple check whether they intersect or not but without calculating the intersection point (likely has something to do with vectors and cross products as they typically do, less with actual logic).

[Maciej Hehl]

It is tempting, at a first glance, to look for some fancy use of vector products and comparing angles, but think about calculations needed to get those products and look at Adam's or Peter's solution. Calculating the determinants for the equation set is almost the same as calculating vector products

[corsiKa]

Lines are not rays. And parallel lines can intersect as well (if they are the same line).

[corsiKa]

The question specifically states that it's limited to 2d.

[Vivin Paliath]

Also if the 2D space is curved, parallel lines can intersect (latitudes and longitudes for example).

[Faken]

Sorry i edited my post to reflect what i was really asking. They lines are actually rays with a starting point but no end. Checking the slope will not give me the answer as it is possible for the "lines" to intersect on the "wrong" side of the point which counts as a miss.

[vicatcu]

@glowcoder It didn't state that at the time that I answered originally, edited post to describe 2-D algorithm.

[Faken]

@glowcoder: its ok, if it was in 3D all i need to do is set all z components to zero and simplify the equations and it should work. Thanks vicatcu, ill check out the site.

[Kurucu]

I believe the question implies that they are not infinite in both directions: they have a starting vector and a direction vector. Thus a line starting at (1,2) and going off on (0,1) will not intersect with a line starting at (2,1) and going off on (1,0). If they were lines rather than 'rays', then of course your answer would be correct.

[John]

Ahh you got it. Didn't see that.

[John]

Don't know if the "edge cases" are necessary to consider but I edited my answer to describe them.

[Faken]

An edge case in my application is very unlikely and even a false positive doesn't really hurt me. I need raw speed since I'm iterating over possibly billions of such cases. I'll just simply say if anything collinear we will just call it an intersection rather than add a few extra statements to nail down exactly what happened.

[Adam Rosenfield]

No, this is wrong. See my comment on John at CashCommons' equally incorrect solution.

[ColacX]

how do you solve u from the last formula? it includes itself.

[Peter Walser]

whoops, I inserted 'v' into the wrong equation. It's fixed now.

[user975989]

I understand this post is old, and I am not sure why or how, but this solution causes different solutions when the vector a and be are switched, notably when the solution would have been v = 2 but it equals 1 instead. The points I used were: for the first vector (7.64475393f, 5.59931898f), (6.30824f, 4.91833f) for the second vector (6.43122959f, 7.98099709f),(6.43122864f, 6.48099709f)

[MarkWeston]

How do you go from as.y + ad.y * u = bs.y + bd.y * ((as.x + ad.x * u - bs.x) / bd.x) to 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) ?

[MarkWeston]

For those who were confused by the derivation, here it is: math.stackexchange.com/questions/2788943

[WDC]

The link has expired.

[jwd]

Small nit: for the case of det==0, it could mean there is no intersection, or it could also mean there is intersection everywhere (the input lines overlap). Perhaps it could more accurately be phrased "the rays do not have a unique intersection".