Линия – пересечение линии - Line–line intersection

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

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

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

Отличительные особенности неевклидова геометрия - это количество и расположение возможных пересечений между двумя линиями и количество возможных линий без пересечений (параллельных линий) с данной линией.

Формулы

Смотрите также: Наклонные линии § Формулы

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

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

Сначала рассмотрим пересечение двух прямых ${displaystyle L_{1},}$ и ${displaystyle L_{2},}$ в 2-х мерном пространстве, с линией ${displaystyle L_{1},}$ определяется двумя разными точками ${displaystyle (x_{1},y_{1}),}$ и ${displaystyle (x_{2},y_{2}),}$, и линия ${displaystyle L_{2},}$ определяется двумя разными точками ${displaystyle (x_{3},y_{3}),}$ и ${displaystyle (x_{4},y_{4}),}$.^[1]

Перекресток ${displaystyle P,}$ линии ${displaystyle L_{1},}$ и ${displaystyle L_{2},}$ можно определить с помощью детерминанты.

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

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

${displaystyle {egin{aligned}(P_{x},P_{y})={igg (}&{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})}},&{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})}}{igg )}end{aligned}}}$

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

${displaystyle L_{1}={x_{1} choose y_{1}}+t{x_{2}-x_{1} choose y_{2}-y_{1}},qquad L_{2}={x_{3} choose y_{3}}+u{x_{4}-x_{3} choose y_{4}-y_{3}}}$

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

${displaystyle t={frac {egin{vmatrix}x_{1}-x_{3}&x_{3}-x_{4}y_{1}-y_{3}&y_{3}-y_{4}end{vmatrix}}{egin{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 {egin{vmatrix}x_{1}-x_{2}&x_{1}-x_{3}y_{1}-y_{2}&y_{1}-y_{3}end{vmatrix}}{egin{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})=(x_{1}+t(x_{2}-x_{1}),;y_{1}+t(y_{2}-y_{1}))quad { ext{or}}quad (P_{x},P_{y})=(x_{3}+u(x_{4}-x_{3}),;y_{3}+u(y_{4}-y_{3}))}$

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

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

${displaystyle (x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})=0.}$

Если линии почти параллельны, то компьютерное решение может столкнуться с числовыми проблемами, реализующими решение, описанное выше: распознавание этого условия может потребовать приблизительной проверки в практическом приложении. Альтернативный подход может заключаться в повороте сегментов линии так, чтобы один из них был горизонтальным, откуда легко получить решение для параметрической формы поворота второй линии. Требуется тщательное обсуждение особых случаев (параллельные линии / совпадающие линии, перекрывающиеся / неперекрывающиеся интервалы).

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

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

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

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

Мы можем изменить это выражение, чтобы извлечь значение ${displaystyle x}$,

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

и так,

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

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

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

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

${displaystyle Pleft({frac {d-c}{a-b}},a{frac {d-c}{a-b}}+cight)}$.

Обратите внимание, если а = б тогда две строки параллельно. Если c ≠ d кроме того, линии разные и пересечения нет, иначе две линии идентичны.

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

Используя однородные координаты, точку пересечения двух неявно определенных прямых можно определить довольно легко. В 2D каждую точку можно определить как проекцию 3D-точки, заданную как упорядоченную тройку ${displaystyle (x,y,w)}$. Преобразование из 3D в 2D координаты ${displaystyle (x',y')=(x/w,y/w)}$. Мы можем преобразовать 2D-точки в однородные координаты, определив их как ${displaystyle (x,y,1)}$.

Предположим, что мы хотим найти пересечение двух бесконечных прямых в 2-мерном пространстве, определяемом как ${displaystyle a_{1}x+b_{1}y+c_{1}=0}$ и ${displaystyle a_{2}x+b_{2}y+c_{2}=0}$. Мы можем представить эти две линии в координаты линии в качестве ${displaystyle U_{1}=(a_{1},b_{1},c_{1})}$ и ${displaystyle U_{2}=(a_{2},b_{2},c_{2})}$,

Перекресток ${displaystyle P'}$ двух строк тогда просто задается^[3]

${displaystyle P'=(a_{p},b_{p},c_{p})=U_{1} imes 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})}$

Если ${displaystyle c_{p}=0}$ линии не пересекаются.

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

Смотрите также: Наклонные линии § Более двух линий

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

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

В двух измерениях более двух линий почти наверняка не пересекаются в одной точке. Чтобы определить, есть ли они, и, если да, чтобы найти точку пересечения, напишите я-е уравнение (я = 1, ...,п) в качестве ${displaystyle (a_{i1}quad a_{i2})(xquad y)^{T}=b_{i},}$ и сложите эти уравнения в матричную форму как

${displaystyle Aw=b,}$

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

${displaystyle w=A^{g}b=(A^{T}A)^{-1}A^{T}b,}$

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

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

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

В трех измерениях линия представлена ​​пересечением двух плоскостей, каждая из которых имеет уравнение вида ${displaystyle (a_{i1}quad a_{i2}quad a_{i3})(xquad yquad z)^{T}=b_{i}.}$ Таким образом, набор п линии могут быть представлены двумяп уравнения в трехмерном координатном векторе ш = (Икс, у, z)^Т:

${displaystyle Aw=b}$

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

${displaystyle w=(A^{T}A)^{-1}A^{T}b.}$

Ближайшие точки к наклонным линиям

Основная статья: Наклонные линии § Ближайшие точки

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

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

В двумерном случае сначала представим линию я как точка, ${displaystyle p_{i}}$, на линии и единица измерения нормальный вектор, ${displaystyle {hat {n}}_{i}}$, перпендикулярно этой линии. То есть, если ${displaystyle x_{1}}$ и ${displaystyle x_{2}}$ точки на прямой 1, тогда пусть ${displaystyle p_{1}=x_{1}}$ и разреши

${displaystyle {hat {n}}_{1}:={egin{bmatrix}0&-11&0end{bmatrix}}(x_{2}-x_{1})/|x_{2}-x_{1}|}$

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

Обратите внимание, что расстояние от точки, Икс к линии ${displaystyle (p,{hat {n}})}$ дан кем-то

${displaystyle d(x,(p,n))=|(x-p)cdot {hat {n}}|=|(x-p)^{ op }{hat {n}}|=|{hat {n}}^{ op }(x-p)|={sqrt {(x-p)^{ op }{hat {n}}{hat {n}}^{ op }(x-p)}}.}$

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

${displaystyle d(x,(p,n))^{2}=(x-p)^{ op }({hat {n}}{hat {n}}^{ op })(x-p).}$

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

${displaystyle E(x)=sum _{i}(x-p_{i})^{ op }({hat {n}}_{i}{hat {n}}_{i}^{ op })(x-p_{i}).}$

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

${displaystyle {egin{aligned}E(x)&=sum _{i}x^{ op }{hat {n}}_{i}{hat {n}}_{i}^{ op }x-x^{ op }{hat {n}}_{i}{hat {n}}_{i}^{ op }p_{i}-p_{i}^{ op }{hat {n}}_{i}{hat {n}}_{i}^{ op }x+p_{i}^{ op }{hat {n}}_{i}{hat {n}}_{i}^{ op }p_{i}&=x^{ op }left(sum _{i}{hat {n}}_{i}{hat {n}}_{i}^{ op }ight)x-2x^{ op }left(sum _{i}{hat {n}}_{i}{hat {n}}_{i}^{ op }p_{i}ight)+sum _{i}p_{i}^{ op }{hat {n}}_{i}{hat {n}}_{i}^{ op }p_{i}.end{aligned}}}$

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

${displaystyle {frac {partial E(x)}{partial x}}=0=2left(sum _{i}{hat {n}}_{i}{hat {n}}_{i}^{ op }ight)x-2left(sum _{i}{hat {n}}_{i}{hat {n}}_{i}^{ op }p_{i}ight)}$

так

${displaystyle left(sum _{i}{hat {n}}_{i}{hat {n}}_{i}^{ op }ight)x=sum _{i}{hat {n}}_{i}{hat {n}}_{i}^{ op }p_{i}}$

и так

${displaystyle x=left(sum _{i}{hat {n}}_{i}{hat {n}}_{i}^{ op }ight)^{-1}left(sum _{i}{hat {n}}_{i}{hat {n}}_{i}^{ op }p_{i}ight).}$

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

Пока ${displaystyle {hat {n}}_{i}}$ не определен более чем в двух измерениях, это можно обобщить на любое количество измерений, отметив, что ${displaystyle {hat {n}}_{i}{hat {n}}_{i}^{ op }}$ представляет собой просто (симметричную) матрицу со всеми собственными значениями, равными единице, за исключением нулевого собственного значения в направлении вдоль линии, обеспечивающей полунорма на расстоянии между ${displaystyle p_{i}}$ и еще одна точка, указывающая расстояние до линии. В любом количестве измерений, если ${displaystyle {hat {v}}_{i}}$ является единичным вектором вдоль то я-я строка, тогда

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

куда я является единичной матрицей, поэтому^[4]

${displaystyle x=left(sum _{i}I-{hat {v}}_{i}{hat {v}}_{i}^{ op }ight)^{-1}left(sum _{i}(I-{hat {v}}_{i}{hat {v}}_{i}^{ op })p_{i}ight).}$

Общее происхождение

Чтобы найти точку пересечения набора прямых, мы вычисляем точку с минимальным расстоянием до них. Каждая линия определяется началом координат ${displaystyle a_{i}}$ и единичный вектор направления, ${displaystyle n_{i}}$. Квадрат расстояния от точки ${displaystyle p}$ к одной из строк дана Пифагора:

${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}}}$

Где : ${displaystyle {left(p-a_{i}ight)}^{T}*n_{i}}$ это проекция: ${displaystyle left(p-{{a}_{i}}ight)}$на линии ${displaystyle i}$. Сумма расстояний от квадрата до всех линий равна:

${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]}$

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

${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}$

${displaystyle {underset {i}{mathop {sum } }},left(p-{{a}_{i}}ight)={underset {i}{mathop {sum } }},left[{{n}_{i}}*{{n}_{i}}^{T}ight]*left(p-{{a}_{i}}ight)}$

Результат:

${displaystyle [{underset {i}{mathop {sum } }},left[I-{{n}_{i}}*{{n}_{i}}^{T}ight]]*p={underset {i}{mathop {sum } }},left[I-{{n}_{i}}*{{n}_{i}}^{T}ight]*{{a}_{i}}}$

Где ${displaystyle I}$ - единичная матрица. Это матрица ${displaystyle ~S*p=C}$, с решением ${displaystyle p={{S}^{+}}*C}$, куда ${displaystyle {S}^{+}}$, является псевдообратным ${displaystyle S}$.

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

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

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

1. "Weisstein, Eric W." Line-Line Intersection. "From MathWorld". Веб-ресурс Wolfram. Получено 2008-01-10.
2. Антонио, Франклин (1992). «Глава IV.6: Более быстрое пересечение отрезков линии». В Кирк, Дэвид (ред.). Графика Самоцветы III. Academic Press, Inc., стр. 199–202. ISBN  0-12-059756-X.
3. «Однородные координаты». robotics.stanford.edu. Получено 2015-08-18.
4. Траа, Йоханнес. "Пересечение линий методом наименьших квадратов" (PDF). Получено 30 августа 2018.

внешняя ссылка

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