Comments 14
Которую можно схлопнуть.
Шорохи в голове подсказывают мне, что "схлопнуть" лучше домножением обоих частей СЛАУ на транспонированную матрицу системы.
А для проверки принадлежности отрезкам нужно проверять, что 0<=s<=1 и 0<=t<=1.
А всего-то и надо было что, решить переопределённую систему из 4 линейных уравнений с 3 неизвестными - определить её совместность и, если да, найти решение.
Кстати, а программа предусматривает вариант совпадения прямых?
Вообще, да, дни школьной алгебры на Хабре…
Вообще обычно нужны ближайшие точки двух прямых. Пересечение - это частный случай, когда эти точки совпадают.
Решается достаточно просто. Даны две прямые:
a(t) = a0 + a * t
b(s) = b0 + b * s
Вектор между ближайшими точками прямых должен быть перпендикулярен обеим прямым. Т.е. имеем систему двух линейных уравнений:
dot(a, a(t) - b(s)) = 0
dot(b, a(t) - b(s)) = 0
Если уравнения линейно зависимы - прямые параллельны. Если нет, решаем, находим t и s. Если расстояние между соответствующим им точками равно нулю - прямые пересекаются, если не равно - это кратчайшее расстояние между прямыми.
Вас в детстве не учили никогда не сравнивать вещественные числа на равенство?
Если бы только автора этой статьи. Для демонстрации что так не надо делать, годится PostGis. Их тоже не учили, и там результат ST_LineInterpolatePoint (возвращает точку на отрезке) часто не принадлежит этому отрезку (в терминах их собственных ST_Contains / ST_Intersect).
С одной стороны, aamonster действительно прав, что вещественные числа при программировании нужно сравнивать не как
a = b, а как (a - b)< eps из-за погрешности вычислений, с другой стороны, лично меня коробит высокомерие, которым пахнет это сообщение
В пространстве размерности 3 и более, искать точное пересечение прямых/отрезков, решая переопределённую СЛАУ, на практике во многих случаях бессмысленно. Зачастую нужно искать приблизительное пересечение. Искать приблизительное пересечение нужно поиском кратчайшего соединительного отрезка (shortest line between two lines/segments).
Подробнее можно почитать тут
С этими вашими тырнетами совсем книги читать разучились... Полистайте Выгодский М.Я. "Справочник по высшей математике". По крайней мере для меня, это настольная (бумажная) книга. И да, в 3D пространстве Вам необходимо не определять точку пересечения, а решать "уравнение общего перпендикуляра к двум данным прямым" (п.164 Выгодского - решение дает ДВЕ точки в пространстве), а уже расстояние между ними должно проверяться на допуск - считать ли это пересечением для вашей задачи.
для любителей геометрической алгебры, вот вам решение в PGA. Работает в любых измерениях>=2.
l1 = P00 v P01
l2 = P10 v P11
Px = l1 ^ l2
if <Px*Px,0> > 0
// пересекаются
len01 = len1 . len1 // dot-product
len0x = (P00 v Px) . l1
if same_sign(len01, len0x) and len0x < len01
// точка внутри отрезка P00-P01
Это вроде дефолтная задача по линалу первого курса
Поиск пересечений между отрезком и прямой или прямой и прямой в трехмерном пространстве