Пересечение линии с линией

Общая точка(ы), разделяемая двумя прямыми в евклидовой геометрии

Две пересекающиеся линии

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

В трехмерной евклидовой геометрии, если две прямые не лежат в одной плоскости , они не имеют точек пересечения ^[1] и называются скрещивающимися прямыми . Однако, если они лежат в одной плоскости, есть три возможности: если они совпадают (не являются различными прямыми), они имеют бесконечное множество общих точек (а именно, все точки на любой из них); если они различны, но имеют одинаковый наклон , они называются параллельными и не имеют общих точек; в противном случае они имеют одну точку пересечения.

Отличительными чертами неевклидовой геометрии являются количество и места возможных пересечений между двумя прямыми, а также количество возможных прямых, не пересекающихся (параллельных прямых) с данной прямой. ^{[ необходимо дополнительное объяснение ]}

Формулы

Необходимым условием пересечения двух прямых является то, что они находятся в одной плоскости, то есть не являются скрещивающимися прямыми. Удовлетворение этого условия эквивалентно тому, что тетраэдр с вершинами в двух точках одной прямой и двух точках другой прямой является вырожденным в смысле нулевого объема . Алгебраическую форму этого условия см. в разделе Скрещивающиеся прямые § Проверка на скрещивание .

Даны две точки на каждой линии

Сначала рассмотрим пересечение двух линий L ₁ и L ₂ в двумерном пространстве, при этом линия L ₁ определяется двумя различными точками ( x ₁ , y ₁ ) и ( x ₂ , y ₂ ) , а линия L ₂ определяется двумя различными точками ( x ₃ , y ₃ ) и ( x ₄ , y ₄ ) . ^[2]

Пересечение P прямых L ₁ и L ₂ можно определить с помощью определителей .

${\displaystyle P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!\qquad P_{y}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!}$

Определители можно записать как:

${\displaystyle {\begin{aligned}P_{x}&={\frac {(x_{1}y_{2}-y_{1}x_{2})(x_{3}-x_{4})-(x_{1}-x_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\\[4px]P_{y}&={\frac {(x_{1}y_{2}-y_{1}x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\end{aligned}}}$

Если две прямые параллельны или совпадают, знаменатель равен нулю.

Даны две точки на каждом отрезке прямой

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

${\displaystyle L_{1}={\begin{bmatrix}x_{1}\\y_{1}\end{bmatrix}}+t{\begin{bmatrix}x_{2}-x_{1}\\y_{2}-y_{1}\end{bmatrix}},\qquad L_{2}={\begin{bmatrix}x_{3}\\y_{3}\end{bmatrix}}+u{\begin{bmatrix}x_{4}-x_{3}\\y_{4}-y_{3}\end{bmatrix}}}$

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

${\displaystyle t={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{3}-x_{4}\\y_{1}-y_{3}&y_{3}-y_{4}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{3}-y_{4})-(y_{1}-y_{3})(x_{3}-x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}}$

и

${\displaystyle u=-{\frac {\begin{vmatrix}x_{1}-x_{2}&x_{1}-x_{3}\\y_{1}-y_{2}&y_{1}-y_{3}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}=-{\frac {(x_{1}-x_{2})(y_{1}-y_{3})-(y_{1}-y_{2})(x_{1}-x_{3})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},}$

с

${\displaystyle (P_{x},P_{y})={\bigl (}x_{1}+t(x_{2}-x_{1}),\;y_{1}+t(y_{2}-y_{1}){\bigr )}\quad {\text{or}}\quad (P_{x},P_{y})={\bigl (}x_{3}+u(x_{4}-x_{3}),\;y_{3}+u(y_{4}-y_{3}){\bigr )}}$

Пересечение будет, если 0 ≤ t ≤ 1 и 0 ≤ u ≤ 1. Точка пересечения попадает в первый отрезок линии, если 0 ≤ t ≤ 1 , и попадает во второй отрезок линии, если 0 ≤ u ≤ 1. Эти неравенства можно проверить без необходимости деления, что позволяет быстро определить существование любого пересечения отрезков линии до вычисления его точной точки. ^[3]

Даны два уравнения линии

Координаты x и y точки пересечения двух невертикальных прямых можно легко найти с помощью следующих подстановок и перестановок.

Предположим, что две линии имеют уравнения y = ax + c и y = bx + d, где a и b — наклоны ( градиенты) линий, а c и d — y -пересечения линий. В точке пересечения двух линий (если они пересекаются) обе координаты y будут одинаковыми, отсюда и следующее равенство:

${\displaystyle ax+c=bx+d.}$

Мы можем перестроить это выражение, чтобы извлечь значение x ,

${\displaystyle ax-bx=d-c,}$

и так,

${\displaystyle x={\frac {d-c}{a-b}}.}$

Чтобы найти координату y , нам нужно всего лишь подставить значение x в одно из двух уравнений прямой, например, в первое:

${\displaystyle y=a{\frac {d-c}{a-b}}+c.}$

Следовательно, точка пересечения — это

${\displaystyle P=\left({\frac {d-c}{a-b}},a{\frac {d-c}{a-b}}+c\right).}$

Обратите внимание, что если a = b , то две прямые параллельны и не пересекаются, если только c = d ; в этом случае прямые совпадают и пересекаются в каждой точке.

Использование однородных координат

Используя однородные координаты , точку пересечения двух неявно определенных линий можно определить довольно легко. В 2D каждая точка может быть определена как проекция 3D точки, заданной как упорядоченная тройка ( x , y , w ) . Отображение из 3D в 2D координаты есть ( x ′, y ′) = ( ⁠х/ж⁠ , ⁠у/ж⁠ ) ​​. Мы можем преобразовать 2D-точки в однородные координаты, определив их как ( x , y , 1) .

Предположим, что мы хотим найти пересечение двух бесконечных прямых в 2-мерном пространстве, определяемое как a ₁ x + b ₁ y + c ₁ = 0 и a ₂ x + b ₂ y + c ₂ = 0 . Мы можем представить эти две прямые в линейных координатах как U ₁ = ( a ₁ , b ₁ , c ₁ ) и U ₂ = ( a ₂ , b ₂ , c ₂ ) . Пересечение P ′ двух прямых тогда просто задается как ^[4]

${\displaystyle P'=(a_{p},b_{p},c_{p})=U_{1}\times U_{2}=(b_{1}c_{2}-b_{2}c_{1},a_{2}c_{1}-a_{1}c_{2},a_{1}b_{2}-a_{2}b_{1})}$

Если c _p = 0 , то прямые не пересекаются.

Более двух строк

Пересечение двух прямых можно обобщить, включив дополнительные прямые. Существование и выражение для проблемы пересечения n прямых следующие.

В двух измерениях

В двух измерениях более двух прямых почти наверняка не пересекаются в одной точке. Чтобы определить, пересекаются ли они, и если да, то найти точку пересечения, запишите i -е уравнение ( i = 1, …, n ) как

${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}=b_{i},}$

и сложить эти уравнения в матричную форму как

${\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} ,}$

где i -я строка матрицы A размером n × 2 равна [ a _{i 1} , a _{i 2} ] , w — вектор размером 2 × 1 [^х
_у] , аi-й элемент вектора-столбца b равен b _i . Если A имеет независимые столбцы, еерангравен 2. Тогда тогда и только тогда, когда ранграсширенной матрицы [ A | b ]также равен 2, существует решение матричного уравнения и, следовательно, точка пересеченияnлиний. Точка пересечения, если она существует, задается как

${\displaystyle \mathbf {w} =\mathbf {A} ^{\mathrm {g} }\mathbf {b} =\left(\mathbf {A} ^{\mathsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\mathsf {T}}\mathbf {b} ,}$

где A ^g — обобщенная обратная матрица Мура–Пенроуза для A (которая имеет указанную форму, поскольку A имеет полный ранг столбца). В качестве альтернативы решение можно найти, совместно решая любые два независимых уравнения. Но если ранг A равен только 1, то если ранг расширенной матрицы равен 2, то решения нет, а если ее ранг равен 1, то все строки совпадают друг с другом.

В трех измерениях

Вышеуказанный подход можно легко распространить на три измерения. В трех или более измерениях даже две прямые почти наверняка не пересекаются; пары непараллельных прямых, которые не пересекаются, называются скрещивающимися прямыми . Но если пересечение существует, его можно найти следующим образом.

В трех измерениях линия представлена ​​пересечением двух плоскостей, каждая из которых имеет уравнение вида

${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}&a_{i3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}=b_{i}.}$

Таким образом, набор из n линий можно представить с помощью 2 n уравнений в трехмерном координатном векторе w :

${\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} }$

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

${\displaystyle \mathbf {w} =\left(\mathbf {A} ^{\mathsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\mathsf {T}}\mathbf {b} .}$

Ближайшие точки к скрещивающимся линиям

PQ, кратчайшее расстояние между двумя скрещивающимися прямыми AB и CD перпендикулярно как AB, так и CD

В двух или более измерениях мы обычно можем найти точку, которая является наиболее близкой к двум или более линиям в смысле наименьших квадратов .

В двух измерениях

В двумерном случае сначала представим линию i как точку p _i на линии и единичный нормальный вектор n̂ _i , перпендикулярный этой линии. То есть, если x ₁ и x ₂ — точки на линии 1, то пусть p ₁ = x ₁ и пусть

${\displaystyle \mathbf {\hat {n}} _{1}:={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}{\frac {\mathbf {x} _{2}-\mathbf {x} _{1}}{\|\mathbf {x} _{2}-\mathbf {x} _{1}\|}}}$

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

Расстояние от точки x до прямой ( p , n̂ ) определяется по формуле

${\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}={\bigl |}(\mathbf {x} -\mathbf {p} )\cdot \mathbf {\hat {n}} {\bigr |}=\left|(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \right|=\left|\mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )\right|={\sqrt {(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )}}.}$

Итак, квадрат расстояния от точки x до прямой равен

${\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}^{2}=(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\left(\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} ).}$

Сумма квадратов расстояний до многих линий представляет собой функцию стоимости :

${\displaystyle E(\mathbf {x} )=\sum _{i}(\mathbf {x} -\mathbf {p} _{i})^{\mathsf {T}}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} _{i}).}$

Это можно переставить:

${\displaystyle {\begin{aligned}E(\mathbf {x} )&=\sum _{i}\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}-\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} +\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\\&=\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)+\sum _{i}\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}.\end{aligned}}}$

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

${\displaystyle {\frac {\partial E(\mathbf {x} )}{\partial \mathbf {x} }}={\boldsymbol {0}}=2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)}$

так

${\displaystyle \left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} =\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}}$

и так

${\displaystyle \mathbf {x} =\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right).}$

В более чем двух измерениях

Хотя n̂ _i не является хорошо определенным в более чем двух измерениях, это можно обобщить на любое число измерений, заметив, что n̂ _i n̂ _i ^T — это просто симметричная матрица со всеми собственными значениями, равными единице, за исключением нулевого собственного значения в направлении вдоль линии, что обеспечивает полунорму на расстоянии между p _i и другой точкой, дающей расстояние до линии. В любом числе измерений, если v̂ _i — единичный вектор вдоль i -й линии , то

${\displaystyle \mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}}$становится ${\displaystyle \mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}}$

где I — единичная матрица , и поэтому ^[5]

${\displaystyle x=\left(\sum _{i}\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)\mathbf {p} _{i}\right).}$

Общий вывод

Чтобы найти точку пересечения набора прямых, мы вычисляем точку с минимальным расстоянием до них. Каждая прямая определяется началом a _i и единичным вектором направления n̂ _i . Квадрат расстояния от точки p до одной из прямых дается из Пифагора:

${\displaystyle d_{i}^{2}=\left\|\mathbf {p} -\mathbf {a} _{i}\right\|^{2}-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}=\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}$

где ( p − a _i ) ^T n̂ _i — проекция p − a _i на линию i . Сумма расстояний до квадрата до всех линий равна

${\displaystyle \sum _{i}d_{i}^{2}=\sum _{i}\left({\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-{\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}\right)}$

Чтобы минимизировать это выражение, продифференцируем его по p .

${\displaystyle \sum _{i}\left(2\left(\mathbf {p} -\mathbf {a} _{i}\right)-2\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)\mathbf {\hat {n}} _{i}\right)={\boldsymbol {0}}}$

${\displaystyle \sum _{i}\left(\mathbf {p} -\mathbf {a} _{i}\right)=\sum _{i}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\left(\mathbf {p} -\mathbf {a} _{i}\right)}$

что приводит к

${\displaystyle \left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\right)\mathbf {p} =\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {a} _{i}}$

где I — единичная матрица . Это матрица Sp = C , с решением p = S ⁺ C , где S ⁺ — псевдообратная матрица S.

Неевклидова геометрия

Слева направо: евклидова геометрия, сферическая геометрия и гиперболическая геометрия.

В сферической геометрии любые два больших круга пересекаются. ^[6]

В гиперболической геометрии для любой прямой и любой точки существует бесконечно много прямых, проходящих через эту точку и не пересекающих данную прямую. ^[6]

Смотрите также

• Пересечение отрезков линий
• Пересечение прямых в проективном пространстве
• Расстояние между двумя параллельными прямыми
• Расстояние от точки до линии
• Пересечение прямой и плоскости
• Параллельный постулат
• Триангуляция (компьютерное зрение)
• Пересечение (евклидова геометрия) § Два отрезка

Ссылки

1. Кук, Джереми (21 ноября 2023 г.). «Компланарные прямые в геометрии | Определение, диаграммы и примеры» . Получено 1 ноября 2024 г.
2. Weisstein, Eric W. "Пересечение прямых". MathWorld . Получено 10.01.2008 .
3. Антонио, Франклин (1992). "Глава IV.6: Более быстрое пересечение отрезков линий". В Kirk, David (ред.). Graphics Gems III . Academic Press, Inc. стр. 199–202. ISBN 0-12-059756-X.
4. Birchfield, Stanley (1998-04-23). ​​"Однородные координаты". robotics.stanford.edu . Архивировано из оригинала 2000-09-29 . Получено 2015-08-18 .
5. Траа, Йоханнес (2013). "Пересечение линий по методу наименьших квадратов" (PDF) . cal.cs.illinois.edu . Архивировано из оригинала (PDF) 2017-09-12 . Получено 2018-08-30 .
6. "Исследование гиперболического пространства" (PDF) . math.berkeley.edu . Получено 2022-06-03 .

Внешние ссылки

• Расстояние между линиями и сегментами с их ближайшей точкой сближения, применимое к двум, трем или более измерениям.