Determining if two rays intersect

Let's assume that the first ray is a, the second ray is b, .s is the ray's starting point (a 2D vector), and .d is the ray's direction (also a 2D vector), and × denotes a 2D cross product, defined as:

a × b = a.x * b.y - a.y * b.x 

After factoring out the common terms, the solution to the intersection equations comes to:

d = b.s - a.s det = b.d × a.d u = d × b.d / det v = d × a.d / det 

If (and only if) det == 0, the rays are parallel and there are zero (or there is an infinite number of) intersection points. The execution of this code would lead to a division by zero.

Otherwise, if both u and v are positive numbers, the rays have a unique intersection point and u is the distance between a.s and the intersection point, while v is the distance between b.s and the intersection point.

After de-vectorizing and inlining the cross product, this becomes:

dx = b.s.x - a.s.x dy = b.s.y - a.s.y det = b.d.x * a.d.y - b.d.y * a.d.x u = (dy * b.d.x - dx * b.d.y) / det v = (dy * a.d.x - dx * a.d.y) / det 

Five subtractions, six multiplications and two divisions.

If you don't care about the intersection point or the distance to it, 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.

On the other hand, if you'd actually want to find the intersection point, you have to input one of these solutions to the respective ray equation.

p = a.s + a.d * u 

...which should be aproximately equal (as far as the numerical precision allows) to...

p = b.s + b.d * v 

c++ for Guntners solution

bool RaysIntersection(const Point& as, const Point& ad, const Point& bs, const Point& bd, Point& result) { if (as == bs) { result = as; return true; } auto dx = bs.X - as.X; auto dy = bs.Y - as.Y; auto det = bd.X * ad.Y - bd.Y * ad.X; if (det != 0) { // near parallel line will yield noisy results double u = (dy * bd.X - dx * bd.Y) / (double)det; double v = (dy * ad.X - dx * ad.Y) / (double)det; if (u >= 0 && v >= 0) { result = as + ad * u; return true; } } return false; } 

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

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

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.

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.

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.