У меня есть два луча на двумерной плоскости, которые простираются до бесконечности, но обе имеют начальную точку. Оба они описываются начальной точкой и вектором в направлении луча, простирающегося до бесконечности. Я хочу узнать, пересекаются ли два луча, но мне не нужно знать, где они пересекаются (это часть алгоритма обнаружения столкновений).
Все, что я рассмотрел до сих пор, описывает обнаружение точки пересечения двух линий или отрезков. Есть ли быстрый алгоритм для решения этой проблемы?
Учитывая: два луча 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
Вставка и решение против 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)
Вычислить u, а затем вычислить v, если оба положительны, лучи пересекаются, иначе не.
Я сожалею, что не согласен с ответом Питера Уолсера. Решение уравнений дается на моем столе:
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 достаточны, и эти два divisons могут быть заменены на num * denom <0 или (sign (num)!= sign (denom)), в зависимости от того, что более эффективно на вашей целевой машине.
Обратите внимание, что редкий случай det == 0 означает, что лучи не пересекаются (одно дополнительное сравнение).
Луч может быть представлен множеством точек 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
}
}
GeomAlgorithms.com имеет некоторые довольно сладкие алгоритмы, связанные с линиями в 3D... В общем случае вероятность того, что две линии пересекаются в 3D-пространство действительно довольно низкое.
В 2D вы должны проверить наклон. Если наклон не равен, то они пересекаются. Если наклон равен, они пересекаются, если точка на них имеет одну и ту же координату x или ту же y-координату.
Линии представлены точкой p и вектором v:
line = p + a * v (для всех a)
Лучи (положительная) половина этой линии:
ray = p + a * v (для всех a >= 0)
Чтобы определить, пересекаются ли две линии, установите их равными и решите:
происходит пересечение, где p 1 + a 1 * v 1= p 2 + a 2 * v 2
(обратите внимание, что есть два неизвестных, 1 и 2, и два уравнения, так как p и v являются многомерными)
Решите для 1 и 2 - если они оба неотрицательны, они пересекаются. Если кто-то отрицательный, они не пересекаются.
Если линии имеют бесконечную длину, они всегда будут пересекаться, если они не параллельны. Чтобы проверить, параллельны ли они, найдите наклон каждой строки и сравните их. Наклон будет просто (y2-y1)/(x2-x1).
Я хочу только проверить, пересекаются ли два луча. Пойду по нему, вычислив направление вращения двух "треугольников", созданных из двух лучей. Они на самом деле не треугольники, но с математической точки зрения, если я только хотел рассчитать поворот треугольника, мне нужны только два вектора с общей начальной точкой, а остальное не имеет значения.
Первый треугольник будет образован двумя векторами и начальной точкой. Отправной точкой будет первая точка начала луча. Первым вектором будет первый вектор направления луча. Второй вектор будет векторным вектором первой начальной точки луча во вторую начальную точку луча. Отсюда возьмем поперечное произведение двух векторов и заметим знак.
Мы снова делаем это для второго треугольника. Опять же, отправной точкой является вторая точка начала луча. Первый вектор представляет собой второе направление лучей, а второй вектор - от второй начальной точки луча до первой начальной точки луча. Возьмем поперечное произведение векторов и заметим знак.
Теперь мы просто берем два знака и проверяем, совпадают ли они. Если они одинаковы, у нас нет пересечений. Если они разные, мы имеем пересечение. Что это!
Вот какой код psudo:
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
Это работает пять умножений, шесть вычитаний и одно сравнение.
Эти ребята из Принстона сделали хороший слайд-шоу об этом. Ответ описан вокруг слайда 17. Я думаю, что это одно и то же решение, описанное в первом комментарии, но оно конденсируется в пару точечных продуктов.