Определение, пересекаются ли два луча

Question

У меня есть два луча в плоскости 2D, которые простираются до бесконечности, но у обоих есть отправная точка. Они оба описываются отправной точкой и вектором в направлении луча, простирающегося до бесконечности. Я хочу выяснить, пересекаются ли два луча, но мне не нужно знать, где они пересекаются (это часть алгоритма обнаружения столкновений).

Все, что я рассмотрел до сих пор, описывает нахождение точки пересечения двух линий или отрезков. Существует ли быстрый алгоритм для решения этой проблемы?

Answer 1

Дано: два луча a, b с начальными точками (исходными векторами) as, bs и векторами направления ad, bd.

Две линии пересекаются, если существует точка пересечения p:

p = as + ad * u
p = bs + bd * v

Если эта система уравнений имеет решение для u> = 0 и v> = 0 (положительное направление - это то, что делает их лучами), лучи пересекаются.

Для координат x / y 2d векторов это означает:

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

Дальнейшие действия:

as.x + ad.x * u = bs.x + bd.x * v
as.y + ad.y * u = bs.y + bd.y * v

Решение против v:

v := (as.x + ad.x * u - bs.x) / bd.x

Вставка и решение против вас:

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)

Рассчитайте u, затем вычислите v, если оба положительны, лучи пересекаются, иначе нет.

Answer 2

Извините, что не согласен с ответом Питера Уолзера. Решение уравнений дает на моем столе:

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)

С учетом общих терминов это означает:

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

Пять вычитаний, шесть умножений и два деления.

Если вам нужно только знать, пересекаются ли лучи, достаточно знаков u и v, и эти два деления можно заменить на num * denom <0 или (знак (num)! = Знак (denom)) в зависимости от того, что является более эффективным на вашей целевой машине. </p>

Обратите внимание, что редкий случай det == 0 означает, что лучи не пересекаются (одно дополнительное сравнение).

Answer 3

Луч может быть представлен набором точек A + Vt, где A - начальная точка, V - вектор, указывающий направление луча, а t >= 0 - параметр. Таким образом, чтобы определить, пересекаются ли два луча, сделайте следующее:

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

Answer 4

Линии представлены точкой p и вектором v :

line = p + a * v (для всех a)

Лучи (положительная) половина этой линии:

ray = p + a * v (для всех a> = 0)

Чтобы определить, пересекаются ли две линии, установите их равными и решите:

пересечение происходит там, где p ₁ + a ₁ * v ₁ = p ₂ + a ₂ * v ₂
(обратите внимание, что есть два неизвестных: ₁ и ₂ , и два уравнения, поскольку p и v ' многомерны)

Решите для ₁ и ₂ - если они оба неотрицательны, они пересекаются. Если кто-то отрицателен, они не пересекаются.

Answer 5

GeomAlgorithms.com имеет несколько довольно приятных алгоритмов, работающих с линиями в 3D ... Вообще говоря, вероятность пересечения двух линий в 3D-пространстве действительно довольно мала.

В 2D вы должны проверить наклон. Если наклон не равен, то они пересекаются. Если наклон равен, они пересекаются, если точка на них имеет одинаковую x-координату или одинаковую y-координату.

Answer 6

Я хочу только проверить, пересекаются ли два луча. Я сделаю это, рассчитав направление вращения двух «треугольников», созданных из двух лучей. На самом деле это не треугольники, но с математической точки зрения, если бы я только хотел вычислить вращение треугольника, мне нужны только два вектора с общей начальной точкой, а остальное не имеет значения.

Первый треугольник будет образован двумя векторами и отправной точкой. Отправная точка будет отправной точкой первого луча. Первый вектор будет вектором направления первого луча. Второй вектор будет вектором от начальной точки первого луча до начальной точки второго луча. Отсюда мы берем перекрестное произведение двух векторов и отмечаем знак.

Мы делаем это снова для второго треугольника. Опять же, отправной точкой является отправная точка второго луча. Первый вектор - это направление второго луча, а второй - от начальной точки второго луча до начальной точки первого луча. Мы снова берем перекрестное произведение векторов и отмечаем знак.

Теперь мы просто берем два знака и проверяем, совпадают ли они. Если они одинаковы, у нас нет пересечения. Если они разные, у нас есть пересечение. Вот и все!

Вот некоторый псевдокод:

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

Получается пять умножений, шесть вычитаний и одно сравнение.

Answer 7

Если линии имеют бесконечную длину, то они всегда пересекаются, если они не параллельны. Чтобы проверить, параллельны ли они, найдите наклон каждой линии и сравните их. Наклон будет просто (y2-y1) / (x2-x1).