Есть несколько способов сделать тест пересечения линия-линия. Классическим способом является использование линейной алгебры (то есть решение линейной матричной системы), но с точки зрения разработки программного обеспечения мне больше нравится способ геометрической алгебры в форме плюкерных координат, который требует только реализации операций векторной алгебры (т.е. перекрестное произведение и точечное произведение), которые проще кодировать, чем матричные операции для решения линейных систем.
Решение векторной алгебры
Данный отрезок линии P ограничен точками P1 и P2, а отрезок линии Q ограничен точками Q1 и Q2.
Параметрическая форма линий определяется как:
P (t) = P1 + t (P2 - P1)
Q (t) = Q1 + t (Q2 - Q1)
Где t - действительное число в интервале [0 1].
Если две линии пересекаются, то имеет место следующее уравнение:
P (t0) = Q (t1)
При условии, что существуют два неизвестных числа t0 и t1. Разложив приведенное выше уравнение, получим:
t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
Чтобы избежать работы с матричной алгеброй, мы можем попытаться решить систему, используя векторную алгебру и метод подстановки:
t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
t0 = a + t1 b
t1 = C • (Q1 - (1 - a) P1 - a P2) / | C | ^ 2
Где:
a = (P2 - P1) • (Q1 - P1) / | P2 - P1 | ^ 2
b = (P2 - P1) • (Q2 - Q1) / | P2 - P1 | ^ 2
C = b (P2 - P1) - (Q2 - Q1)
Где (•) - скалярное произведение. Точка пересечения P (t0) (или Q (t1)) существует, если t0 и t1 находятся в интервале [0 1].
Путь к Плюккеру
Дан отрезок P, ограниченный точками P1 и P2, и отрезок Q, ограниченный точками Q1 и Q2.
Координаты Плюккера линии P задаются парой 3d векторов (Pd, Pm):
Pd = P2 - P1
Pm = P1 × P2
Где Pm - это перекрестное произведение P1 и P2. Координаты Плюккера (Qd, Qm) линии Q можно рассчитать точно так же.
Линии P и Q могут пересекаться только в том случае, если они копланарны. Линии P и Q копланарны, если:
Pd • Qm + Qd • Pm = 0
Где (•) - скалярное произведение. Поскольку машины имеют конечную точность, надежный тест должен проверять не ноль, а небольшое число. Если Pd × Qd = 0, то линии параллельны (здесь 0 - нулевой вектор). Опять же, следует провести надежный тест, чтобы убедиться, что квадрат длины (Pd × Qd) мал.
Если линии не параллельны, то они копланарны, и их точка пересечения (называемая «встречаться» на жаргоне Плюккера) будет точкой:
x = ((Pm • N) Qd - (Qm • N) Pd - (Pm • Qd) N) / (Pd × Qd) • N
Где N - любой вектор координатной оси (т. Е. (1,0,0) или (0,1,0) или (0,0,1)), так что (Pd × Qd) • N не является нуль.
Если ни P, ни Q не пройдут через начало координат, то их координаты Плюккера Pm и Qm соответственно будут ненулевыми, и будет работать следующая формула синплера
x = Pm × Qm / Pd • Qm
Для ознакомления с координатами Плюккера см .:
https://en.m.wikipedia.org/wiki/Plücker_coordinates
http://www.realtimerendering.com/resources/RTNews/html/rtnv11n1.html#art3
Общую формулу пересечения см. В «Следствии 6»:
http://web.cs.iastate.edu/~cs577/handouts/plucker-coordinates.pdf
Линейный путь алгебры
Дан отрезок P, ограниченный точками P1 и P2, и отрезок Q, ограниченный точками Q1 и Q2.
Параметрическая форма линий определяется как:
P (t) = P1 + t (P2 - P1)
Q (t) = Q1 + t (Q2 - Q1)
Где t - действительное число в интервале [0 1].
Если две линии пересекаются, то выполняется следующее уравнение:
P (t0) = Q (t1)
При условии, что существуют два неизвестных числа t0 и t1. Разложив приведенное выше уравнение получим:
t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
Мы можем решить для t0 и t1, выразив вышеприведенное уравнение в матричной алгебре:
A x = B
ГдеA - матрица 3x2 с координатами вектора (P2 - P1) в первом столбце и координатами вектора (Q2 - Q1) во втором столбце; x - вектор столбца 2x1 с неизвестными t0 и t1, а B - вектор столбца 3x1 с координатами вектора (Q1 - P1).
Классически система может быть решена путем вычисления псевдообратной матрицы A, обозначаемой A ^ +:
A ^ + = (A ^ T A) ^ - 1 A ^ T
См:
https://en.m.wikipedia.org/wiki/Generalized_inverse
К счастью, любой матричный пакет в Python должен иметь возможность очень легко и, возможно, очень эффективно вычислять вышеуказанные вычисления.
Если умножение A на его псевдообратный A ^ + равно единичной матрице I, т. Е. (AA ^ +) == I, то существует ЕДИНСТВЕННЫЙ ответ (пересечение), и вы можете получить его, вычисляя следующее продукта:
x = A ^ + B
Конечно, если вы не можете сначала вычислить псевдообратное, например, потому что (A ^ T A) единственное число (то есть определитель равен нулю), то пересечения не существует.
Поскольку мы имеем дело с отрезками, точка пересечения находится в точке P (x0) или Q (x1), если x0 и x1 оба находятся в интервале [0 1].