Пересечение линий
В евклидовой геометрии пересечение прямой и прямой может быть пустым множеством , точкой или другой линией . Различение этих случаев и поиск пересечений находят применение, например, в компьютерной графике , планировании движения и обнаружении столкновений .
В трехмерной евклидовой геометрии, если две прямые не лежат в одной плоскости , они не имеют точки пересечения. [ нужна ссылка ] и называются косыми линиями . Однако если они находятся в одной плоскости, есть три возможности: если они совпадают (не являются отдельными линиями), они имеют бесконечное количество общих точек (а именно, все точки на любой из них); если они различны, но имеют одинаковый наклон , то говорят, что они параллельны и не имеют общих точек; в противном случае они имеют одну точку пересечения.
Отличительными признаками неевклидовой геометрии являются количество и расположение возможных пересечений двух прямых и количество возможных прямых без пересечений (параллельных линий) с данной прямой. [ нужны дальнейшие объяснения ]
Формулы
[ редактировать ]пересечения Необходимым условием двух линий является то, что они находятся в одной плоскости, то есть не являются наклонными линиями. Удовлетворение этого условия эквивалентно тому, что тетраэдр с вершинами в двух точках на одной прямой и в двух точках на другой прямой вырожден в смысле нулевого объема . Алгебраическую форму этого условия см. в разделе «Наклонные линии» § Проверка на асимметрию .
Даны две точки в каждой строке
[ редактировать ]пересечение двух линий и 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 ] нет, и уникальное пересечение, если оно существует, определяется выражением
Ближайшие точки к наклонным линиям
[ редактировать ]В двух или более измерениях мы обычно можем найти точку, которая взаимно ближе всего к двум или более линиям в смысле наименьших квадратов .
В двух измерениях
[ редактировать ]В двумерном случае сначала представьте линию i как точку p i на прямой и единичный вектор нормали n̂ i , перпендикулярный этой линии. То есть, если x 1 и x 2 являются точками на прямой 1, то пусть p 1 = x 1 и пусть
который является единичным вектором вдоль линии, повернутой на прямой угол.
Расстояние от точки x до линии ( p , n̂ ) определяется выражением
Итак, квадрат расстояния от точки x до прямой равен
Сумма квадратов расстояний до многих линий представляет собой функцию стоимости :
Это можно переставить:
Чтобы найти минимум, продифференцируем по x и приравняем результат к нулевому вектору:
так
и так
В более чем двух измерениях
[ редактировать ]Хотя n̂ i не определен четко более чем в двух измерениях, это можно обобщить на любое количество измерений, отметив, что n̂ i n̂ i Т представляет собой просто симметричную матрицу со всеми собственными значениями, за исключением нулевого собственного значения в направлении вдоль линии, обеспечивающего полунорму расстояния между pi и другой точкой , задающей расстояние до линии. В любом количестве измерений, если v̂ i — единичный вектор вдоль -й прямой i , то
- становится
где I — единичная матрица , и так [4]
Общий вывод
[ редактировать ]Чтобы найти точку пересечения набора прямых, вычисляем точку с минимальным расстоянием до них. Каждая линия определяется началом координат a i и единичным вектором направления n̂ i . Квадрат расстояния от точки p до одной из прямых дан у Пифагора:
где ( п - а я ) Т n̂ i — это проекция p − a i на линию i . Сумма расстояний от квадрата до всех линий равна
Чтобы минимизировать это выражение, продифференцируем его по p .
что приводит к
где I — единичная матрица . Это матрица Sp = C с решением p = S + C , где S + является псевдообратным S .
Неевклидова геометрия
[ редактировать ]Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( июнь 2022 г. ) |
В сферической геометрии любые два больших круга пересекаются. [5]
В гиперболической геометрии , если дана любая линия и любая точка, через эту точку проходит бесконечно много прямых, не пересекающих данную прямую. [5]
См. также
[ редактировать ]- Пересечение сегментов линии
- Пересечение линий в проективном пространстве
- Расстояние между двумя параллельными линиями
- Расстояние от точки до линии
- Пересечение линии и плоскости
- Постулат параллельности
- Триангуляция (компьютерное зрение)
- Пересечение (евклидова геометрия) § Два отрезка
Ссылки
[ редактировать ]- ^ Вайсштейн, Эрик В. «Пересечение линий-линий» . Математический мир . Проверено 10 января 2008 г.
- ^ Антонио, Франклин (1992). «Глава IV.6: Пересечение сегментов более быстрой линии». В Кирке, Дэвиде (ред.). Графические драгоценности III . Academic Press, Inc., стр. 199–202. ISBN 0-12-059756-Х .
- ^ Берчфилд, Стэнли (23 апреля 1998 г.). «Однородные координаты» . robotics.stanford.edu . Архивировано из оригинала 29 сентября 2000 г. Проверено 18 августа 2015 г.
- ^ Траа, Йоханнес (2013). «Пересечение линий методом наименьших квадратов» (PDF) . Cal.cs.illinois.edu . Архивировано из оригинала (PDF) 12 сентября 2017 г. Проверено 30 августа 2018 г.
- ^ Jump up to: Перейти обратно: а б «Исследование гиперболического пространства» (PDF) . math.berkeley.edu . Проверено 3 июня 2022 г.
Внешние ссылки
[ редактировать ]- Расстояние между линиями и сегментами с их ближайшей точкой сближения , применимо к двум, трем или более измерениям.