Jump to content

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

(Перенаправлено из «Две пересекающиеся линии »)
Две пересекающиеся линии

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

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

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

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

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

[ редактировать ]

пересечение двух линий и x1 L2 в ( пространстве, причем линия определяется L1 двумя различными x2 , линия y1 ) является и рассмотрим , y2 L1 точками ) Сначала мы , а L2 ( двумерном определяется двумя различными точками ( x 3 , y 3 ) и ( x 4 , y 4 ) . [1]

Пересечение P линий L 1 и L 2 можно определить с помощью определителей .

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

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

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

[ редактировать ]

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

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

и

с

Пересечение произойдет, если 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 будут одинаковыми, отсюда следует следующее равенство:

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

и так,

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

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

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

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

[ редактировать ]

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

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

Если c p = 0 , линии не пересекаются.

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

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

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

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

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

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

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

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

[ редактировать ]

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

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

Расстояние от точки x до линии ( p , ) определяется выражением

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

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

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

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

так

и так

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

[ редактировать ]

Хотя i не определен четко более чем в двух измерениях, это можно обобщить на любое количество измерений, отметив, что i i Т представляет собой просто симметричную матрицу со всеми собственными значениями, за исключением нулевого собственного значения в направлении вдоль линии, обеспечивающего полунорму расстояния между pi и другой точкой , задающей расстояние до линии. В любом количестве измерений, если i — единичный вектор вдоль -й прямой i , то

становится

где I единичная матрица , и так [4]

Общий вывод

[ редактировать ]

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

где ( п - а я ) Т i — это проекция p a i на линию i . Сумма расстояний от квадрата до всех линий равна

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

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

где 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. ^ Jump up to: Перейти обратно: а б «Исследование гиперболического пространства» (PDF) . math.berkeley.edu . Проверено 3 июня 2022 г.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: bdc2c363c10c9a3864ab4dcf12888f6a__1718633280
URL1:https://arc.ask3.ru/arc/aa/bd/6a/bdc2c363c10c9a3864ab4dcf12888f6a.html
Заголовок, (Title) документа по адресу, URL1:
Line–line intersection - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)