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?

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

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.

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.

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

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.

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