Определение, если два луча пересекаются
У меня есть два луча на 2D плоскости, которые расширяются на бесконечность, но у обоих есть начальная точка. Они и описаны начальной точкой и вектором в направлении луча, расширяющегося на бесконечность. Я хочу узнать, пересекаются ли два луча, но я не должен знать, где они пересекаются (это - часть алгоритма обнаружения коллизий).
Все, на что я посмотрел до сих пор, описывает нахождение точки пересечения двух строк или линейных сегментов. Существует ли алгоритм FAST для решения этого?
7 ответов
Дано: два луча a, b с начальными точками (исходными векторами) as, bs и векторами направления ad, bd.
Две прямые пересекаются, если есть точка пересечения p:
p = as + ad * u
p = bs + bd * v
Если эта система уравнений имеет решение для u> = 0 и v> = 0 (положительное направление делает их лучи), лучи пересекаются.
Для координат x / y двумерных векторов это означает:
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, если оба положительны, лучи пересекаются, иначе - нет.
Если линии имеют бесконечную длину, они будут всегда пересекаться, если только они не параллельны. Чтобы проверить, параллельны ли они, найдите наклон каждой линии и сравните их. Наклон будет просто (y2-y1) / (x2-x1).
Мне жаль не согласиться с ответом Питера Уолсера. Решение уравнений дает на моем столе:
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 или (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... Вообще говоря, вероятность пересечения двух линий в трехмерном пространстве очень мала.
В 2D нужно проверять наклон. Если наклон не равен, то они пересекаются. Если наклон равен, то они пересекаются, если точка на них имеет одну и ту же координату x или одну и ту же координату y.
Я хочу только проверить, пересекаются ли два луча. Я займусь этим, вычислив направление вращения двух «треугольников», созданных из двух лучей. На самом деле это не треугольники, но с математической точки зрения, если бы я только хотел вычислить вращение треугольника, мне понадобились бы только два вектора с общей начальной точкой, а все остальное не имеет значения.
Первый треугольник будет образован двумя векторами и начальной точкой. Отправной точкой будет начальная точка первого луча.Первый вектор будет вектором направления первого луча. Второй вектор будет вектором от начальной точки первого луча до начальной точки второго луча. Отсюда мы берем произведение двух векторов и отмечаем знак.
Проделаем то же самое со вторым треугольником. Опять же, отправная точка - это отправная точка второго луча. Первый вектор - это направление второго луча, а второй вектор - от начальной точки второго луча до начальной точки первого луча. Снова возьмем векторное произведение векторов и отметим знак.
Теперь мы просто берем два знака и проверяем, совпадают ли они. Если они одинаковые, у нас нет пересечения. Если они разные, у нас есть пересечение. Вот и все!
Вот какой-то псудокод:
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
Он состоит из пяти умножений, шести вычитаний и одного сравнения.
Линии представлены точкой p и вектором v:
line = p + a * v (для всех a)
Лучи - (положительная) половина этой линии:
ray = p + a * v (для всех a >= 0)
Чтобы определить, пересекаются ли две прямые, задайте их равными и решите:
пересечение происходит там, где p1 + a1 * v1 = p2 + a2 * v2
(обратите внимание, что здесь два неизвестных, a1 и a2, и два уравнения, поскольку p's и v's многомерны)
Решите для a1 и a2 - если они оба неотрицательны, они пересекаются. Если один из них отрицательный, то они не пересекаются.