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

Общая точка (точки) двух линий в евклидовой геометрии.

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

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

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

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

Формулы

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

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

_{Сначала мы рассмотрим} пересечение двух линий L1 и L2 в двумерном пространстве , причем линия _L1 определяется двумя различными _{точками} ( x1 _, y1 ₎ и ( x2 _, y2 ) , а _линия L2 _{является} определяется двумя различными точками ( x ₃ , y ₃ ) и ( x ₄ , y ₄ ) . ^[1]

Пересечение 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 . Эти неравенства можно проверить без необходимости деления, что позволяет быстро определить наличие пересечения любого отрезка линии перед вычислением его точной точки. ^[2]

Учитывая два линейных уравнения

Координаты 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 ′ двух прямых тогда просто определяется формулой ^[3]

${\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 — это просто симметричная матрица со всеми собственными значениями, равными единице, за исключением нулевого собственного значения в направлении вдоль линия, обеспечивающая полунорму расстояния между pi и другой точкой _, задающей расстояние до линии. В любом количестве измерений, если 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 — единичная матрица , и так ^[4]

${\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.

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

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

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

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

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

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

Рекомендации

1. Вайсштейн, Эрик В. «Пересечение линий». Математический мир . Проверено 10 января 2008 г.
2. Антонио, Франклин (1992). «Глава IV.6: Пересечение сегментов более быстрой линии». В Кирке, Дэвиде (ред.). Графические драгоценности III . Academic Press, Inc., стр. 199–202. ISBN 0-12-059756-Х.
3. Берчфилд, Стэнли (23 апреля 1998 г.). «Однородные координаты». robotics.stanford.edu . Архивировано из оригинала 29 сентября 2000 г. Проверено 18 августа 2015 г.
4. Траа, Йоханнес (2013). «Пересечение линий методом наименьших квадратов» (PDF) . Cal.cs.illinois.edu . Архивировано из оригинала (PDF) 12 сентября 2017 г. Проверено 30 августа 2018 г.
5. «Исследование гиперболического пространства» (PDF) . math.berkeley.edu . Проверено 3 июня 2022 г.

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

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