Пересечение линий.
В Евклидова геометрия, то пересечение из линия и линия может быть пустой набор, а точка, или строку. Выделение этих случаев и нахождение точки пересечения полезно, например, в компьютерная графика, планирование движения, и обнаружение столкновения.
В трехмерный Евклидова геометрия, если две прямые не совпадают самолет они называются косые линии и не имеют точки пересечения. Если они находятся в одной плоскости, есть три возможности: если они совпадают (не являются разными линиями), у них есть бесконечность общих точек (а именно всех точек на любой из них); если они различны, но имеют одинаковый наклон, их называют параллельно и не имеют общих точек; в противном случае они имеют единую точку пересечения.
Отличительные особенности неевклидова геометрия - это количество и расположение возможных пересечений между двумя линиями и количество возможных линий без пересечений (параллельных линий) с данной линией.
Формулы
А необходимое условие для двух пересекающихся линий означает, что они находятся в одной плоскости, то есть не являются наклонными. Выполнение этого условия равносильно тетраэдр с вершинами в двух точках на одной прямой и двумя точками на другой прямой выродиться в смысле нулевого объем. Алгебраическую форму этого условия см. Наклонные линии § Проверка на перекос.
Учитывая две точки на каждой строке
Сначала рассмотрим пересечение двух прямых
и
в 2-х мерном пространстве, с линией
определяется двумя разными точками
и
, и линия
определяется двумя разными точками
и
.[1]
Перекресток
линии
и
можно определить с помощью детерминанты.

Детерминанты можно записать как:

Обратите внимание, что точка пересечения предназначена для бесконечно длинных линий, определяемых точками, а не для отрезки линии между точками, и может создать точку пересечения, превышающую длину отрезков линии. Чтобы найти положение пересечения по отношению к отрезкам линии, мы можем определить линии
и
с точки зрения первой степени Безье параметры:

(куда т и ты являются действительными числами). Точка пересечения линий находится при одном из следующих значений: т или же ты, куда

и

с:

Точка пересечения попадает в первый отрезок прямой, если 0,0 ≤т ≤ 1,0, и он попадает во второй отрезок линии, если 0,0 ≤ты ≤ 1,0. Эти неравенства можно проверить без деления, что позволяет быстро определить наличие пересечения любого отрезка прямой до вычисления его точной точки.[2]
Когда две прямые параллельны или совпадают, знаменатель равен нулю:

Если линии почти параллельны, то компьютерное решение может столкнуться с числовыми проблемами, реализующими решение, описанное выше: распознавание этого условия может потребовать приблизительной проверки в практическом приложении. Альтернативный подход может заключаться в повороте сегментов линии так, чтобы один из них был горизонтальным, откуда легко получить решение для параметрической формы поворота второй линии. Требуется тщательное обсуждение особых случаев (параллельные линии / совпадающие линии, перекрывающиеся / неперекрывающиеся интервалы).
Учитывая два линейных уравнения
В
и
координаты точки пересечения двух невертикальных прямых можно легко найти с помощью следующих замен и перестановок.
Предположим, что две прямые имеют уравнения
и
куда
и
являются склоны (градиенты) линий и где
и
являются у-перехваты линий. В точке пересечения двух линий (если они пересекаются) обе
координаты будут такими же, отсюда и следующее равенство:
.
Мы можем изменить это выражение, чтобы извлечь значение
,
,
и так,
.
Чтобы найти у координаты, все, что нам нужно сделать, это подставить значение Икс в одно из двух линейных уравнений, например, в первое:
.
Следовательно, точка пересечения
.
Обратите внимание, если а = б тогда две строки параллельно. Если c ≠ d кроме того, линии разные и пересечения нет, иначе две линии идентичны.
Использование однородных координат
Используя однородные координаты, точку пересечения двух неявно определенных прямых можно определить довольно легко. В 2D каждую точку можно определить как проекцию 3D-точки, заданную как упорядоченную тройку
. Преобразование из 3D в 2D координаты
. Мы можем преобразовать 2D-точки в однородные координаты, определив их как
.
Предположим, что мы хотим найти пересечение двух бесконечных прямых в 2-мерном пространстве, определяемом как
и
. Мы можем представить эти две линии в координаты линии в качестве
и
,
Перекресток
двух строк тогда просто задается[3]

Если
линии не пересекаются.
Более двух строк
Пересечение двух линий может быть обобщено для включения дополнительных линий. Существование и выражение для пЗадачи пересечения линий заключаются в следующем.
В двух измерениях
В двух измерениях более двух линий почти наверняка не пересекаются в одной точке. Чтобы определить, есть ли они, и, если да, чтобы найти точку пересечения, напишите я-е уравнение (я = 1, ...,п) в качестве
и сложите эти уравнения в матричную форму как

где я-й ряд п × 2 матрица А является
, ш - вектор 2 × 1 (х, у)Т, а я-й элемент вектора-столбца б является бя. Если А имеет независимые столбцы, его классифицировать равно 2. Тогда тогда и только тогда, когда ранг расширенная матрица [А | б ] также равно 2, существует решение матричного уравнения и, следовательно, точка пересечения п линий. Точка пересечения, если она существует, задается формулой

куда
это Обобщенное обратное Мура-Пенроуза из
(который имеет показанную форму, потому что А имеет полный ранг столбца). В качестве альтернативы решение может быть найдено путем совместного решения любых двух независимых уравнений. Но если ранг А равен только 1, то если ранг расширенной матрицы равен 2, решения нет, но если его ранг равен 1, то все строки совпадают друг с другом.
В трех измерениях
Вышеупомянутый подход можно легко расширить до трех измерений. В трех или более измерениях даже две линии почти наверняка не пересекаются; пары непараллельных прямых, которые не пересекаются, называются косые линии. Но если пересечение действительно существует, его можно найти следующим образом.
В трех измерениях линия представлена пересечением двух плоскостей, каждая из которых имеет уравнение вида
Таким образом, набор п линии могут быть представлены двумяп уравнения в трехмерном координатном векторе ш = (Икс, у, z)Т:

где сейчас А 2п × 3 и б 2п × 1. Как и раньше, существует единственная точка пересечения тогда и только тогда, когда А имеет полный ранг столбца и расширенную матрицу [А | б ] нет, и единственное пересечение, если оно существует, задается формулой

Ближайшие точки к наклонным линиям
В двух или более измерениях мы обычно можем найти точку, которая взаимно ближе всего к двум или более линиям в наименьших квадратов смысл.
В двух измерениях
В двумерном случае сначала представим линию я как точка,
, на линии и единица измерения нормальный вектор,
, перпендикулярно этой линии. То есть, если
и
точки на прямой 1, тогда пусть
и разреши

который представляет собой единичный вектор вдоль линии, повернутой на 90 градусов.
Обратите внимание, что расстояние от точки, Икс к линии
дан кем-то

Итак, квадрат расстояния от точки, Икс, к строке

Сумма квадратов расстояний до многих линий - это функция стоимости:

Это можно изменить:

Чтобы найти минимум, продифференцируем по Икс и установите результат равным нулевому вектору:

так

и так

Более чем в двух измерениях
Пока
не определен более чем в двух измерениях, это можно обобщить на любое количество измерений, отметив, что
представляет собой просто (симметричную) матрицу со всеми собственными значениями, равными единице, за исключением нулевого собственного значения в направлении вдоль линии, обеспечивающей полунорма на расстоянии между
и еще одна точка, указывающая расстояние до линии. В любом количестве измерений, если
является единичным вектором вдоль то я-я строка, тогда
становится 
куда я является единичной матрицей, поэтому[4]

Общее происхождение
Чтобы найти точку пересечения набора прямых, мы вычисляем точку с минимальным расстоянием до них. Каждая линия определяется началом координат
и единичный вектор направления,
. Квадрат расстояния от точки
к одной из строк дана Пифагора:
![{displaystyle d_ {i} ^ {2} = {{left [left | p - {{a} _ {i}} ight | ight]} ^ {2}} - {{left [{{left (p- { {a} _ {i}} ight)} ^ {T}} * {{n} _ {i}} ight]} ^ {2}} = {{left (p - {{a} _ {i}}) ight)} ^ {T}} * left (p - {{a} _ {i}} ight) - {{left [{{left (p - {{a} _ {i}} ight)} ^ {T }} * {{n} _ {i}} ight]} ^ {2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cce6ab542bc838d7fdd7c221086d54b79438ec76)
Где :
это проекция:
на линии
. Сумма расстояний от квадрата до всех линий равна:
![{displaystyle {underset {i} {mathop {sum}}}, d_ {i} ^ {2} = {underset {i} {mathop {sum}}}, left [{{left (p - {{a} _ {i}} ight)} ^ {T}} * left (p - {{a} _ {i}} ight) - {{left [{{left (p - {{a} _ {i}} ight)) } ^ {T}} * {{n} _ {i}} ight]} ^ {2}} ight]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/826ea130f757e6f4759f41b3905f2452d1659ffb)
Чтобы минимизировать это выражение, продифференцируем его по
.
![{displaystyle {underset {i} {mathop {sum}}}, left [2 * left (p - {{a} _ {i}} ight) -2 * ight [{{left (p - {{a} _) {i}} ight)} ^ {T}} * {{n} _ {i}}] * {{n} _ {i}}] = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88dc9b6afb099b69ef1670dbe49409488e934e36)
![{displaystyle {underset {i} {mathop {sum}}}, left (p - {{a} _ {i}} ight) = {underset {i} {mathop {sum}}}, left [{{n}]) _ {i}} * {{n} _ {i}} ^ {T} ight] * влево (p - {{a} _ {i}} ight)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dd33cbc551e150164ebfb8ec356b009e4239e8d)
Результат:
![{displaystyle [{underset {i} {mathop {sum}}}, слева [I - {{n} _ {i}} * {{n} _ {i}} ^ {T} ight]] * p = { нижняя часть {i} {mathop {sum}}}, слева [I - {{n} _ {i}} * {{n} _ {i}} ^ {T} ight] * {{a} _ {i} }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2f4919e8ae2cb304c0f174bcad9b3a4a446038)
Где
- единичная матрица. Это матрица
, с решением
, куда
, является псевдообратным
.
Смотрите также
Рекомендации
внешняя ссылка