В евклидовой геометрии , то пересечение из линии и линия может быть пустым множеством , А точка , или линия. Выявление этих случаев и определение точки пересечения можно использовать, например, в компьютерной графике , планировании движения и обнаружении столкновений .
В трехмерной евклидовой геометрии, если две прямые находятся не в одной плоскости, они называются косыми линиями и не имеют точки пересечения. Если они находятся в одной плоскости, есть три возможности: если они совпадают (не являются различными линиями), у них есть бесконечное количество общих точек (а именно, все точки на любой из них); если они различны, но имеют одинаковый наклон, то говорят, что они параллельны и не имеют общих точек; в противном случае они имеют единую точку пересечения.
Отличительными чертами неевклидовой геометрии являются количество и расположение возможных пересечений между двумя линиями и количество возможных линий без пересечений (параллельных линий) с данной линией.
Необходимое условие для двух линий пересекаются в том , что они находятся в той же плоскости, то есть не являются косыми линиями. Выполнение этого условия равносильно тому, что тетраэдр с вершинами в двух точках на одной прямой и двумя точками на другой прямой является вырожденным в смысле нулевого объема . Чтобы узнать об алгебраической форме этого условия, см. Склонные линии § Проверка на асимметрию .
Учитывая две точки на каждой строке
Сначала рассмотрим пересечение двух прямых а также в 2-х мерном пространстве, с линией определяется двумя разными точками а также , и линия определяется двумя разными точками а также . [1]
Перекресток линии а также можно определить с помощью определителей .
Детерминанты можно записать как:
где знаменатель:
Когда две прямые параллельны или совпадают, знаменатель равен нулю. Если линии почти параллельны, то компьютерное решение может столкнуться с числовыми проблемами, реализующими решение, описанное выше: распознавание этого условия может потребовать приблизительной проверки в практическом приложении. Альтернативный подход может состоять в том, чтобы повернуть линейные сегменты так, чтобы один из них был горизонтальным, откуда легко получить решение повернутой параметрической формы второй линии. Требуется тщательное обсуждение особых случаев (параллельные линии / совпадающие линии, перекрывающиеся / неперекрывающиеся интервалы).
Учитывая две точки на каждом отрезке линии
Обратите внимание, что точка пересечения выше предназначена для бесконечно длинных линий, определяемых точками, а не для отрезков линий между точками, и может образовывать точку пересечения, не содержащуюся ни в одном из двух отрезков линии. Чтобы найти положение пересечения по отношению к отрезкам линии, мы можем определить линии а также с точки зрения параметров Безье первой степени :
(где t и u - действительные числа). Точка пересечения линий находится при одном из следующих значений t или u , где
а также
с участием:
Точка пересечения попадает в первый сегмент прямой, если 0,0 ≤ t ≤ 1,0, и во второй сегмент, если 0,0 ≤ u ≤ 1,0. Эти неравенства могут быть проверены без необходимости деления, что позволяет быстро определить наличие любого пересечения отрезков прямой до вычисления его точной точки. [2]
Учитывая два линейных уравнения
В а также координаты точки пересечения двух невертикальных прямых можно легко найти с помощью следующих замен и перестановок.
Предположим, что две прямые имеют уравнения а также где а также являются склоны (градиенты) линий и где а также - точки пересечения линий y . В точке пересечения двух линий (если они пересекаются) обе координаты будут такими же, отсюда и следующее равенство:
Мы можем изменить это выражение, чтобы извлечь значение ,
и другие,
Чтобы найти координату y , все, что нам нужно сделать, это подставить значение x в любое из двух линейных уравнений, например, в первое:
Следовательно, точка пересечения
Обратите внимание, если a = b, то две прямые параллельны . Если также c ≠ d , линии разные и пересечения нет, в противном случае две прямые идентичны.
Использование однородных координат
Используя однородные координаты , можно довольно легко определить точку пересечения двух неявно определенных линий. В 2D каждую точку можно определить как проекцию 3D точки, заданную как упорядоченную тройку. Преобразование из 3D в 2D-координаты выполняется следующим образом:. Мы можем преобразовать 2D-точки в однородные координаты, определив их как.
Предположим, что мы хотим найти пересечение двух бесконечных прямых в 2-мерном пространстве, определяемом как а также . Мы можем представить эти две линии в линейных координатах как а также ,
Перекресток двух строк тогда просто дается, [3]
Если линии не пересекаются.
Пересечение двух линий можно обобщить, чтобы включить дополнительные линии. Существование и выражение проблемы пересечения n- линий следующие.
В двух измерениях
В двух измерениях более двух линий почти наверняка не пересекаются в одной точке. Чтобы определить, есть ли они, и, если да, чтобы найти точку пересечения, запишите i-е уравнение ( i = 1,…, n ) как и сложите эти уравнения в матричную форму как
где i-я строка матрицы A размера n × 2 равна, w - вектор ( x, y ) T размером 2 × 1 , а i-й элемент вектора-столбца b - это b i . Если A имеет независимые столбцы, его ранг равен 2. Тогда тогда и только тогда ранг расширенной матрицы [ A | b ] также равно 2, существует решение матричного уравнения и, следовательно, точка пересечения n прямых. Точка пересечения, если она существует, задается формулой
где является обобщенным обращением Мура-Пенроуза к(который имеет показанную форму, потому что A имеет полный ранг столбца). В качестве альтернативы решение может быть найдено путем совместного решения любых двух независимых уравнений. Но если ранг A равен только 1, то если ранг расширенной матрицы равен 2, решения нет, но если его ранг равен 1, то все строки совпадают друг с другом.
В трех измерениях
Вышеупомянутый подход можно легко расширить до трех измерений. В трех или более измерениях даже две линии почти наверняка не пересекаются; пары непараллельных прямых, которые не пересекаются, называются косыми . Но если пересечение действительно существует, его можно найти следующим образом.
В трех измерениях линия представлена пересечением двух плоскостей, каждая из которых имеет уравнение вида Таким образом, набор из n линий может быть представлен 2 n уравнениями в трехмерном координатном векторе w = ( x , y , z ) T :
где теперь A равно 2 n × 3, а b равно 2 n × 1. Как и раньше, существует единственная точка пересечения тогда и только тогда, когда A имеет полный ранг столбца и расширенную матрицу [ A | b ] нет, а единственное пересечение, если оно существует, задается формулой
В двух или более измерениях мы обычно можем найти точку, которая взаимно наиболее близка к двум или более линиям в смысле наименьших квадратов .
В двух измерениях
В двумерном случае сначала представьте линию i как точку,, на прямой и единичный вектор нормали ,, перпендикулярно этой линии. То есть, если а также - точки на прямой 1, тогда пусть и разреши
который представляет собой единичный вектор вдоль линии, повернутой на 90 градусов.
Обратите внимание, что расстояние от точки x до линии дан кем-то
Итак, квадрат расстояния от точки x до линии равен
Сумма квадратов расстояний до многих линий - это функция стоимости :
Это можно изменить:
Чтобы найти минимум, продифференцируем по x и положим результат равным нулевому вектору:
так
и другие
Более чем в двух измерениях
Пока не имеет четкого определения более чем в двух измерениях, это можно обобщить на любое количество измерений, отметив, что представляет собой просто (симметричную) матрицу со всеми собственными значениями, равными единице, за исключением нулевого собственного значения в направлении вдоль линии, обеспечивающей полунорму на расстоянии междуи еще одна точка, указывающая расстояние до линии. В любом количестве измерений, еслиединичный вектор вдоль на я ю линии, то
- становится
где I - единичная матрица, и поэтому [4]
Общее происхождение
Чтобы найти точку пересечения набора прямых, мы вычисляем точку с минимальным расстоянием до них. Каждая линия определяется началом координат и единичный вектор направления, . Квадрат расстояния от точки к одной из строк дается Пифагор:
Где : это проекция на линии . Сумма расстояний от квадрата до всех линий равна:
Чтобы минимизировать это выражение, продифференцируем его по .
Это приводит к:
Где - единичная матрица. Это матрица, с решением , где является псевдообратным к .