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

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

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

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

Формулы

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

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

Сначала мы рассматриваем пересечение двух прямых и в 2-мерном пространстве, при этом прямая определяется двумя разными точками и , а прямая определяется двумя разными точками и . ${\ displaystyle L_ {1}}$${\ displaystyle L_ {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})}$

Пересечение прямой и можно определить с помощью определителей . ${\ displaystyle P}$${\ displaystyle L_ {1}}$${\ displaystyle L_ {2}}$

${\ 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 {align} (P_ {x}, P_ {y}) = {\ Biggl (} & {\ 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})} {D}}, \\ & {\ 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})} {D}} {\ Biggr)} \ end {выровнено}}}$

где знаменатель:

${\ Displaystyle D = (x_ {1} -x_ {2}) (y_ {3} -y_ {4}) - (y_ {1} -y_ {2}) (x_ {3} -x_ {4}) }$

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

Учитывая две точки на каждом отрезке линии

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

${\ 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_ {3} & x_ {1} -x_ {2} \\ y_ {1} -y_ {3} & y_ {1} -y_ { 2} \ 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_ {1} -y_ {2}) - (y_ {1} -y_ {3}) (x_ {1} -x_ {2})} {(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 {\ text {или}} \ quad (P_ {x}, P_ {y}) = (x_ {3} + u (x_ {4} -x_ {3}), \; y_ { 3} + u (y_ {4} -y_ {3}))}$

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

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

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

Предположим , что две линии имеют уравнения и где и являются склоны (градиенты) линий и где и являются у -intercepts линий. В точке пересечения двух линий (если они пересекаются) обе координаты будут одинаковыми, отсюда следующее равенство: ${\ 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 = dc,}$

так что,

${\ displaystyle x = {\ frac {dc} {ab}}.}$

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

${\ displaystyle y = a {\ frac {dc} {ab}} + c.}$

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

${\ displaystyle P \ left ({\ frac {dc} {ab}}, a {\ frac {dc} {ab}} + c \ right).}$

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

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

Используя однородные координаты , можно довольно легко определить точку пересечения двух неявно определенных линий. В 2D каждая точка может быть определена как проекция 3D точки, заданной как упорядоченная тройка . Преобразование из 3D в 2D координаты есть . Мы можем преобразовать 2D-точки в однородные координаты, определив их как . ${\ Displaystyle (х, у, ш)}$${\ Displaystyle (х ', у') = (х / ш, у / ш)}$${\ Displaystyle (х, у, 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 '}$

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

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

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

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

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

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

${\ displaystyle Aw = b,}$

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

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

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

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

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

В трехмерном пространстве линия представлена ​​пересечением двух плоскостей, каждая из которых имеет уравнение вида. Таким образом, набор из n линий может быть представлен 2 n уравнениями в трехмерном координатном векторе w = ( x , y , z ) ^T : ${\ displaystyle {\ begin {bmatrix} a_ {i1} & a_ {i2} & a_ {i3} \ end {bmatrix}} {\ begin {bmatrix} x & y & z \ end {bmatrix}} ^ {\ mathsf {T}} = b_ {я}.}$

${\ displaystyle Aw = b}$

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

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

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

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

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

В двумерном случае, во- первых, представляют собой линию я в качестве отправной точки, на прямой и единичной нормали вектора , перпендикулярно к этой линии. То есть, если и являются точками на прямой 1, то пусть и пусть ${\ displaystyle p_ {i}}$ ${\ Displaystyle {\ шляпа {п}} _ {я}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle p_ {1} = x_ {1}}$

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

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

Обратите внимание, что расстояние от точки x до линии определяется выражением ${\ Displaystyle (п, {\ шляпа {п}})}$

${\ displaystyle d (x, (p, n)) = | (xp) \ cdot {\ hat {n}} | = \ left | (xp) ^ {\ top} {\ hat {n}} \ right | = \ left | {\ hat {n}} ^ {\ top} (xp) \ right | = {\ sqrt {(xp) ^ {\ top} {\ hat {n}} {\ hat {n}} ^ {\ top} (xp)}}.}$

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

${\ displaystyle d (x, (p, n)) ^ {2} = (xp) ^ {\ top} \ left ({\ hat {n}} {\ hat {n}} ^ {\ top} \ right ) (xp).}$

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

${\ displaystyle E (x) = \ sum _ {i} (x-p_ {i}) ^ {\ top} \ left ({\ hat {n}} _ {i} {\ hat {n}} _ { i} ^ {\ top} \ right) (x-p_ {i}).}$

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

${\ displaystyle {\ begin {align} E (x) & = \ sum _ {i} x ^ {\ top} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} xx ^ {\ top} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} p_ {i} -p_ {i} ^ {\ top } {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} x + p_ {i} ^ {\ top} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} p_ {i} \\ & = x ^ {\ top} \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} \ right) x-2x ^ {\ top} \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} p_ {i} \ right) + \ sum _ {i} p_ {i} ^ {\ top} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} p_ {i}. \ end {align}}}$

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

${\ displaystyle {\ frac {\ partial E (x)} {\ partial x}} = 0 = 2 \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n} } _ {i} ^ {\ top} \ right) x-2 \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ вверх} p_ {i} \ right)}$

так

${\ displaystyle \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} \ right) x = \ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} p_ {i}}$

так что

${\ displaystyle x = \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} \ right) ^ {- 1} \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} p_ {i} \ right).}$

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

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

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

где I - единичная матрица, и поэтому

${\ displaystyle x = \ left (\ sum _ {i} I - {\ hat {v}} _ {i} {\ hat {v}} _ {i} ^ {\ top} \ right) ^ {- 1 } \ left (\ sum _ {i} \ left (I - {\ hat {v}} _ {i} {\ hat {v}} _ {i} ^ {\ top} \ right) p_ {i} \ Правильно).}$

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

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

${\ Displaystyle d_ {я} ^ {2} = \ left \ | p-a_ {i} \ right \ | ^ {2} - \ left [\ left (p-a_ {i} \ right) ^ {\ mathsf {T}} * n_ {i} \ right] ^ {2} = \ left (p-a_ {i} \ right) ^ {\ mathsf {T}} * \ left (p-a_ {i} \ right) - \ left [\ left (p-a_ {i} \ right) ^ {\ mathsf {T}} * n_ {i} \ right] ^ {2}}$

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

${\ displaystyle \ sum _ {i} d_ {i} ^ {2} = \ sum _ {i} \ left [{\ left (p-a_ {i} \ right) ^ {\ mathsf {T}}} * \ left (p-a_ {i} \ right) - {\ left [\ left (p-a_ {i} \ right) ^ {\ mathsf {T}} * n_ {i} \ right] ^ {2}} \Правильно]}$

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

${\ displaystyle \ sum _ {i} \ left [2 * \ left (p-a_ {i} \ right) -2 * \ right [{{\ left (p-a_ {i} \ right)} ^ {\ mathsf {T}}} * n_ {i}] * n_ {i}] = 0}$

${\ displaystyle \ sum _ {i} \ left (p-a_ {i} \ right) = \ sum _ {i} \ left [n_ {i} * n_ {i} ^ {\ mathsf {T}} \ right ] * \ left (p-a_ {i} \ right)}$

Результат:

${\ displaystyle \ left [\ sum _ {i} \ left [I- {n_ {i}} * {n_ {i}} ^ {\ mathsf {T}} \ right] \ right] * p = \ sum _ {i} \ left [I- {n_ {i}} * {n_ {i}} ^ {\ mathsf {T}} \ right] * {a_ {i}}}$

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

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

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

использованная литература

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

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