Для теста пересечения линии есть несколько способов решения.Классическим способом является использование линейной алгебры (то есть решение линейной матричной системы), но с точки зрения разработки программного обеспечения мне больше нравится способ геометрической алгебры в форме плюкерных координат, который требует только реализации операций векторной алгебры (т.е.перекрестное произведение и точечное произведение), которые проще для кодирования, чем матричные операции для решения линейных систем.
Я покажу оба для сравнения, а затем вы решите:
ЛинейныйПуть алгебры
Заданный отрезок 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 ^ TA) ^ - 1 A ^ T
См .: https://en.m.wikipedia.org/wiki/Generalized_inverse
К счастью, любой матричный пакет в Java должен бытьспособен вычислять вышеупомянутые вычисления очень легко и, возможно, очень эффективно.
Если умножение A на его псевдообратный A ^ + равно единичной матрице I, т. е. (AA ^ +) == I,тогда есть уникальный ответ (пересечение), и вы можете получить его, вычисляя следующий продукт:
x = A ^ + B
Конечно, если вы не можете вычислить псевдообратное в первомнапример, потому что (A ^ TA) является единственным (т.е. определитель равен нулю), то пересечения не существует.
Поскольку мы имеем дело с отрезками, точка пересечения находится в точке P (x0) или Q (x1) если x0 и x1 оба находятся в интервале [0 1].
ДРУГОЙ МЕТОД РЕШЕНИЯN
Чтобы избежать работы с матричной алгеброй, мы можем попытаться решить систему, используя векторную алгебру и метод подстановки:
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)
Я пока не могу представить геометрическую интуицию приведенных выше результатов.
Plucker Координирует путь
Заданный отрезок P ограничен точками P1 и P2, а отрезок Q ограничен точками Q1 и Q2.
Координаты Плюккера линии P задаются парой 3d векторов (Pd, Pm):
Pd = P2 - P1
Pm = P1 x P2
Где Pm - это перекрестное произведение P1 и P2.Координаты Плюккера (Qd, Qm) линии Q можно рассчитать точно таким же образом.
Линии P и Q могут пересекаться только в том случае, если они копланарны.Линии P и Q являются копланарными, если:
Pd • Qm + Qd • Pm = 0
Где (•) - скалярное произведение.Поскольку машины имеют конечную точность, надежный тест должен проверять не ноль, а небольшое число.Если Pd x Qd = 0, то линии параллельны (здесь 0 - нулевой вектор).Опять же, надежный тест должен быть для подтверждения того, что квадрат длины (Pd x Qd) мал.
Если линии не параллельны, то они копланарны и их пересечение (называемое "встретиться" на жаргоне Плюккера) будетбыть точкой:
x = ((Pm • N) Qd - (Qm • N) Pd - (Pm • Qd) N) / (Pd x Qd) • N
где N - любой вектор координатной оси (т. Е. (1,0,0)) или (0,1,0) или (0,0,1)), так что (Pd x Qd) • N не равно нулю.
Если ни P, ни Q не проходят через начало координат, то их координаты Плюккера Pm и Qm соответственно будут ненулевыми, и следующая формула синплера будет работать
x = Pm x 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
Преобразование эллипсов в круги вперед и назад
Мы всегда можем преобразовать эллипс в круг.Эллипс имеет два «радиуса», называемых полуосями, которые вы можете визуализировать в своем уме как два ортогональных вектора, один большой, называемый большими полуосями, и один маленький, называемый второстепенными полуосями.Вы можете применить неравномерное масштабное преобразование к обоим полуосевым векторам, чтобы сделать их равными по размеру, чтобы получить круг.
Мы определяем эллипс "E" по центру O, который является трехмернымточка и ее две полуоси A1 и A2, которые также являются трехмерными векторами.Нормальный вектор N к плоскости эллипса может быть вычислен по перекрестному произведению его полуосей N = A1 x A2, а затем нормализован так, чтобы он имел единичную длину.
А пока предположим, что существует линейная функция M, котораявы можете использовать для преобразования (масштабирования) вашего эллипса E в круг C с радиусом, равным второстепенным полуосям, применяя его к полуосям A1 и A2 вашего эллипса и к центру эллипса O.
Обратите внимание, что центр O эллипса и нормальный вектор N эллипса не изменяются на M. Таким образом, M (N) = N и M (O) = O. Это означает, что окружность находится в одной плоскости и имеет то же положение C, что иэллипсЛинейная функция M имеет соответствующую обратную функцию M ^ -1, поэтому мы можем преобразовать векторы круга обратно, чтобы получить исходный эллипс E.
Конечно, мы можем преобразовать конечные точки линий P и Q, также используяфункция M для отправки их в «пространство круга», и мы можем отправить их обратно в «пространство эллипса», используя M ^ -1.
Используя M, мы можем вычислить пересечение прямых P и Q с эллипсом E в круговом пространстве.Так что теперь мы можем сосредоточиться на пересечении линии с окружностью.
Пересечение линии с плоскостью
Задана плоскость с вектором нормали N и расстоянием D, таким что:
N • x + D = 0
Для каждой точки x на плоскости.Тогда пересечение с линией P с координатами Плюккера (Pd, Pm) имеет вид:
x = (N x Pm - D Pd) / N • Pd
Это работает, только если линияP не в плоскости, т. Е.:
(N • P1 + D)! = 0 и (N • P2 + D)! = 0
И для нашего эллипса E имеем:
N = (A1 x A2) / | A1 x A2 |
D = -N • O
Пересечение линии-окружности и точки-окружности
Теперь, имея x, проверить точку в окружности легко:
| O - x |<= | A2 | </p>
Равенство выполняется только тогда, когда x находится на границе окружности.
Если линия P находится на плоскости окружности, то следующая проверка на сингулярность даст вам ответ:
https://stackoverflow.com/a/1079478/9147444
Как вычислить линейную функцию M
Простой способ вычисления M заключается в следующем.Используйте вектор нормали эллипса N и полуоси A1 и A2, чтобы создать матрицу 3x3 U. Так, чтобы векторы U векторов A1, A2 и N были столбцами.
Затем масштабируйте главные полуоси A1, чтобы получитьтакой же длины до второстепенных полуосей A2.Затем создайте матрицу V, так как V имеет новые векторы A1 и A2 и N в качестве столбцов.
Затем мы определяем линейную матричную систему:
RU = V
Где R - матрица масштабного вращения 3x3 (неоднородная).
Мы можем решить для R, умножив обе части уравнения на обратную величину U, которая обозначается как U ^ -1
RUU ^ -1 = VU ^ -1
Так как UU ^-1 этоматрицу тождеств мы получаем:
R = VU ^ +
Используя R, мы определяем аффинное преобразование
M (x) = R (x - O) + O
Мы можем использовать M для преобразования точек в окружности, такие как O, P1, P2, Q1 и Q2.Но если нам нужно преобразовать векторы, такие как A1, A2, N, Pd и Qd.Нам нужно использовать более простой M:
M (x) = R x
Поскольку A1, A2 и N являются собственными векторами R, то R не является сингулярным и имеет обратное.Мы определяем обратное M как:
M ^ -1 (x) = R ^ -1 (x - O) + O
И для векторов:
M ^-1 (x) = R ^ -1 x
Обновление: пересечение эллипса с эллипсом
У двух пересекающихся некомпланарных 3d-эллипсов есть точки пересечения на прямойобразуется пересечение между их плоскостями.Таким образом, вы сначала находите линию, образованную пересечением плоскостей, содержащих эллипсы (если плоскости не пересекаются, т. Е. Они параллельны, то и эллипсы не пересекаются).
Линия пересечения принадлежит обеим плоскостям, поэтому она перпендикулярна обеим нормалям.Вектор направления V является перекрестным произведением плоских нормалей:
V = N1 × N2
Чтобы полностью определить линию, нам также нужно найти точку на линии.Мы можем сделать это, решая линейные уравнения плоскостей.Учитывая матрицу 2x3 N = [N1 ^ T N2 ^ T] с нормалями N1 и N2 в качестве строк и вектор столбца 2x1 b = [N1 • C1, N2 • C2], где C1 и C2 - центры эллипсов, мы можем сформировать линейную матричную систему:
NX = b
Где X - некоторая точка, удовлетворяющая обоим уравнениям плоскости.Система недоопределена, поскольку на линии имеется бесконечное число точек, удовлетворяющих системе.Мы все еще можем найти конкретное решение ближе к началу координат, используя псевдообратную матрицу N, обозначаемую N ^ +.
X = N ^ + b
Уравнение линии есть
L (t) = X + t V
Для некоторого скалярного т.
Затем вы можете применить метод, описанный ранее, для проверки пересечения линии-эллипса, т.е. масштабированияэллипс к кругу и пересекается с копланарной линией.Если оба эллипса пересекают линию в одних и тех же точках, то они пересекаются.
Теперь случай, когда эллипсы фактически лежат на одной плоскости, является более сложным.Вы можете подтвердить подход доктора Эберли в его превосходной книге «Геометрические инструменты» (также доступной в Интернете):
https://www.geometrictools.com/Documentation/IntersectionOfEllipses.pdf
А также вы можете проверить открытый исходный код C ++, который открытисточник:
https://www.geometrictools.com/GTEngine/Include/Mathematics/GteIntrEllipse2Ellipse2.h