Как найти координаты точки пересечения отрезка

Не такая тривиальная задача, скажу я вам. Всякий раз, когда возникает необходимость посчитать координату пересечения пары прямых, каждая из которых задана парой точек, снова беру блокнот и вывожу пару формул. И всякий раз – блин, ну это уже когда-то было, опять надо что-то делать с параллельными прямыми, опять появляется пакостная строго вертикальна линия, когда на (x₁-x₂) никак не разделить и т.д.

Поэтому – в подборку теории и практики, пригодится, сэкономим блокнот, спасем дерево.

Коэффициенты А, B, C

Все помним со школы формулу:

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

Те же фаберже, только сбоку.

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

Загвоздка в том, что мы не знаем коэффициенты для обеих линий.

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

Путем несложных операций приходим к следующей записи:

Глядя на вариант в исполнении высшего образования, получаем следующие формулы для нахождения коэффициентов:

Пока все идет отлично, нигде вероятного деления на ноль не встретилось.

Итак, мы можем легко найти два набора коэффициентов для первой и второй прямых. Переходим к системе уравнений.

Система уравнений

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

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

Сразу же запишем метод под нашу систему.

Имеем следующую систему:

Определители будут такими:

Исходя из метода, решение выглядит так:

Ага! Вот и возможное деление на ноль, скажете вы. И правильно! В этой, в высшей степени непозволительной ситуации, когда знаменатель равен нулю, решения нет, прямые либо параллельны, либо совпадают (что, впрочем, частный случай параллельности).  В коде, естественно, этот момент надо учитывать.

Практика 1

Частные случаи

• Прямые параллельны: ∆_ab = 0
  • (A₁B₂ – B₁A₂ = 0);
• Прямые совпадают:  ∆_ab = ∆_X = ∆_Y = 0 
  • (A₁B₂ – B₁A₂ = 0) И (A₁C₂ — A₂C₁ = 0) И (C₁B₂ -B₁C₂ = 0);
• Прямые перпендикулярны:
  • (A₁ A₂ + B₁ B₂ = 0).

Принадлежность точки отрезку

В общем случае, чтобы определить принадлежность точки отрезку, надо установить две вещи:

1. Точка принадлежит прямой, проходящей через конечные точки отрезка. Для этого достаточно подставить значение X и Y в уравнение прямой и проверить получившееся равенство. В нашем случае, этот пункт уже выполнен, т.к. точка пересечения априори принадлежит обеим прямым.
2. Проверить факт нахождения точки между концами отрезка.

Займемся пунктом 2. Данный факт можно установить двумя способами:

• Логически, т.е. (x₁ <= x <= x₂) ИЛИ (x₁ >= x >= x₂). На случай «вертикальности» линии добавить проверку на Y:
  • (y₁ <= y <= y₂) ИЛИ (y₁ >= y >= y₂).
• Арифметически. Сумма отрезков |x-x₁| + |x-x₂| должна быть равна длине отрезка |x₁-x₂|. Аналогично, на случай «вертикальности» , добавить проверку:
  • |y-y₁| + |y-y₂| = |y₁-y₂|

Практика показывает, что арифметический способ быстрее примерно в 3 раза. Когда-то я считал, что операции сравнения самые быстрые. Это давно уже не так.

Задача нахождения принадлежности точки P(x,y) отрезку, заданного двумя точками с координатами P1(x1, y1) и P2(x2, y2) подробно рассмотрена в отдельной статье.

Угол пересечения прямых

Угол пересечения прямых — это угол пересечения направляющих векторов. Т.е., взяв уже знакомые ранее точки p₁ и p₂, получим направляющий вектор V(p₁,p₂), и аналогично второй вектор M(p₃,p₄). В теории мы должны вычислить достаточно «затратную» функцию, с корнями, квадратами, дробями и арккосинусом.

Давайте не будем останавливаться на ней, она долгая, нудная и в нашем случае ненужная. Рассмотрим вектор:

α — угол наклона вектора к оси X, который можно найти, как:

α = arctan (A₁ / B₁)

Где расстояния:

A₁ = (y₁ — y₂)

B₁ = (x₂ — x₁)

Что-то знакомое? Да это ни что иное, как коэффициенты в уравнении прямой от образованных фанатов. Может они и правы в своем испепеляющем фанатизме…

Одним словом, коэффициенты (расстояния) у нас уже есть по обеим прямым.

Судя по рисунку, угол между векторами, это сумма углов наклона векторов к оси X. Ммм… не совсем так, на самом деле это разность.

По рисунку явно видно, что угол между векторам это γ = (β — α).

В предыдущем примере все правильно, просто знаки углов разные, т.к. находятся по разные стороны от оси X, а формула работает та же.

От теории к практике

Теперь в плане практического применения. Мне нужно точно знать, откуда, куда и в каком направлении этот угол. В теории, углом между прямыми считается наименьший из пары γ и (180-γ). Так вот, нам это не надо. Какой угол получится – такой нам и нужен.

Поэтому, под углом между векторами понимаем угол от вектора V(p1,p2) к вектору M(p3,p4). Если знак угла – отрицательный, понимаем, что он против часовой стрелки, иначе – по часовой стрелке.

Следует заметить, что, зная коэффициенты, для нахождения угла пересечения, координаты уже не нужны. Листинг таков:

Тут ситуация с вертикальной прямой, т.е. когда теоретически происходит деление на ноль, явно не обрабатывается. Она корректно обрабатывается функцией ArcTan2, которая вернет в этом случае и знак, и 90 градусов.  

Практика 2

В дополнение к функции нахождения точки пересечения, напишем «продвинутую» функцию, которая находит эту точку, определяет нахождение на каждом из отрезков, и определяет угол между направляющими векторами. Или же определяет, что прямые параллельны/совпадают.

Исходники

Небольшие комментарии по интерфейсу.

Скачать (219 Кб): Исходники (Delphi XE 7-10)

Скачать (1.14 Мб): Исполняемый файл

При запуске генерируется случайным образом 4 точки, по две на прямую. Точки и отрезки можно перетаскивать мышкой. Также, слева присутствует панель, на которой можно ввести координаты точек или коэффициенты уравнения прямой. При нажатии «Enter» или когда элемент ввода теряет фокус, происходит перерасчет и перерисовка.

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

Если точка пересечений попадает в какой-либо из отрезков, соответствующий заголовок линии отрезка станет жирным. На рисунке это зеленая линия 2.

По умолчанию, рабочее поле системы координат имеет размерность [-10..10], которую можно изменить ползунком в нижнем правом углу.

Пересечение в евклидовой геометрии — точка или кривая, общие для двух или более объектов (таких как кривые, плоскости и поверхности). Простейший случай — пересечение двух различных прямых на плоскости, которое либо является одной точкой, либо не существует, если прямые параллельные.

Задача нахождения пересечения плоскостей — двумерных линейных геометрических объектов, встроенных в многомерное пространство — сводится к решению системы линейных уравнений.

В общем случае, пересечение определяется системой нелинейных уравнений, которая може быть решена численно, например, с использованием метода Ньютона. Задачи о пересечении прямой и конического сечения (круг, эллипс, парабола и т. д. ) или квадрики (сфера, цилиндр, гиперболоид и т. д. ) приводят к квадратным уравнениям, которые легко решаются. Пересечения между квадриками приводят к уравнениям четвёртой степени, которые можно решить алгебраически.

На плоскости[править | править код]

Две линии[править | править код]

Для определения точки пересечения двух непараллельных прямых:

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

.

(Если , то эти линии параллельны, а это значит, что эти формулы нельзя использовать, так как они предполагают деление на 0.)

Два отрезка[править | править код]

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

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

Его можно решить для s и t с помощью правила Крамера (см. выше). Если выполняется условие , то вставляется или в соответствующее параметрическое представление и получается точка пересечения .

Пример: Для отрезков и получается линейная система

и . Это означает: линии пересекаются в точке .

Примечание: Рассматривая прямые, а не отрезки, определяемые парами точек, каждое условие может быть опущено, и метод даёт точку пересечения линий (см. выше).

Линия и круг[править | править код]

Для пересечения отрезка и окружности решают линейное уравнение для x или y и подставляют в уравнение окружности и получают решение (используя формулу квадратного уравнения) с:

,

,

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

Если выполняется , то существует только одна точка пересечения и прямая касается окружности. Если слабое неравенство не выполняется, линия не пересекает окружность.

Если середина круга не является началом координат^[1], можно рассматривать пересечение прямой и параболы или гиперболы.

Две окружности[править | править код]

Определение точек пересечения двух окружностей:

сводится к предыдущему случаю пересечения прямой и окружности. Путём вычитания двух данных уравнений получается линейное уравнение:

Эта особая линия является радикальной осью двух окружностей.

Особый случай ; в этом случае начало координат — это центр первого круга, а второй центр лежит на оси абсцисс (см. диаграмму^{[уточнить]}). Уравнение радикальной прямой упрощается до:
а точки пересечения можно записать как с

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

Любой общий случай, как написано выше, можно превратить сдвигом и поворотом в частный случай.

Пересечение двух кругов (внутренности двух окружностей) образует форму, называемую линзой^[en].

Два конических сечения[править | править код]

Задача пересечения эллипса, гиперболы, параболы с другим коническим сечением сводится к системе квадратных уравнений, которую в частных случаях легко решить, исключив одну координату. Специальные свойства конических сечений могут быть использованы для получения решения. В общем, точки пересечения могут быть определены путём решения уравнения с помощью итерации Ньютона. Если а) обе коники заданы неявно (посредством уравнения), необходима двумерная итерация Ньютона; б) одна неявно, а другая параметрически — необходимо, чтобы была задана 1-мерная итерация Ньютона.

Две плавные кривые[править | править код]

Две кривые в (двумерном пространстве), которые непрерывно дифференцируемы (то есть нет резкого изгиба),
имеют точку пересечения, если они имеют общую точку плоскости и имеют в этой точке

a: разные касательные (трансверсальное пересечение) или

b: касательная линия общая, и они пересекают друг друга (касание пересечения, см. диаграмму).

Если обе кривые имеют общую точку S и касательную, но не пересекают друг друга, они просто «касаются» в точке S.

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

• Если заданы обе кривые явно: , приравнивание их даёт уравнение

• Если заданы обе кривые параметрически:

Приравнивая их, получаем два уравнения с двумя переменными:

• Если заданы одна кривая параметрически, а другая неявно:

Это простейший случай помимо явного. Нужно вставить параметрическое представление в уравнение кривой , и получится уравнение:

• Если заданы обе кривые неявно:

Здесь точка пересечения — это решение системы

Любая итерация Ньютона требует удобных начальных значений, которые можно получить, визуализировав обе кривые. Параметрически или явно заданная кривая может быть легко визуализирована, потому что для любого параметра t или x соответственно легко вычислить соответствующую точку. Для неявно заданных кривых эта задача не так проста. В этом случае необходимо определить точку кривой с помощью начальных значений и итерации^[2].

Примеры:

1: и окружность (см диаграмму).

Итерация Ньютона для функции

должна быть выполнена. В качестве начальных значений можно выбрать −1 и 1.5.

Точки пересечения: (−1.1073, −1.3578), (1.6011, 4.1046)

2:

(см диаграмму).

Итерация Ньютона

должна быть выполнена, где является решением линейной системы

в точке . В качестве начальных значений можно выбрать (−0.5, 1) и (1, −0.5).

Линейная система может быть решена по правилу Крамера.

Точками пересечения являются (−0.3686, 0.9953) и (0.9953, −0.3686).

Два многоугольника[править | править код]

Если кто-то хочет определить точки пересечения двух многоугольников, можно проверить пересечение любой пары линейных сегментов многоугольников (см. выше). Для многоугольников с большим количеством сегментов этот метод довольно трудоёмок. На практике алгоритм пересечения ускоряется с помощью оконных тестов. В этом случае можно разделить многоугольники на маленькие подполигоны и определить наименьшее окно (прямоугольник со сторонами, параллельными осям координат) для любого подполигона. Перед началом трудоёмкого определения точки пересечения двух отрезков линии любая пара окон проверяется на наличие общих точек^[3]

В пространстве (три измерения)[править | править код]

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

Линия и плоскость[править | править код]

Пересечение прямой и плоскости в общем положении в трёх измерениях является точкой.

Обычно линия в пространстве представляется параметрически , а плоскость — уравнением . Вставка представления параметра в уравнение даёт линейное уравнение

для параметра точки пересечения .

Если линейное уравнение не имеет решения, либо прямая лежит на плоскости, либо параллельна ей.

'x1,y1,z1, x2,y2,z2, x3,y3,z3 - координаты заданной плоскости
'x4,y4,z4, x5,y5,z5 - координаты заданной прямой

'Коэффициенты для уравнения плоскости
A = y1*(z2 - z3) + y2*(z3 - z1) + y3*(z1 - z2)
B = z1*(x2 - x3) + z2*(x3 - x1) + z3*(x1 - x2)
C = x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2)
D = -1*(x1*(y2*z3 - y3*z2) + x2*(y3*z1 - y1*z3) + x3*(y1*z2 - y2*z1))

'Нормальный вектор к заданной плоскости
xN = A
yN = B
zN = C

'Вспомогательный вектор
xV = x1-x4
yV = y1-y4
zV = z1-z4

'Расстояние до плоскости по нормали
dist1 = xN*xV + yN*yV + zN*zV

'Вспомогательный вектор
xW = x5-x4
yW = y5-y4
zW = z5-z4

'Приближение к плоскости по нормали
dist2 = xN*xW + yN*yW + zN*zW

'Проверка на параллельность
IF dist1 <> 0 THEN 'Прямая не принадлежит плоскости
	IF dist2 <> 0 THEN 'Прямая не параллельна плоскости

		'Вспомогательное отношение
		ratio = dist1/dist2

		'Вспомогательный вектор
		xW = xW*ratio
		yW = yW*ratio
		zW = zW*ratio

		'Искомые координаты
		x0 = x4 + xW
		y0 = y4 + yW
		z0 = z4 + zW
	END IF
END IF

Три плоскости[править | править код]

Если линия определяется двумя пересекающимися плоскостями и должна пересекаться третьей плоскостью , необходимо оценить общую точку пересечения трёх плоскостей.

Три плоскости с линейно независимыми нормальными векторами имеют точку пересечения

Для доказательства следует установить используя правила тройного скалярного произведения. Если тройное скалярное произведение равно 0, то плоскости либо не имеют тройного пересечения, либо это прямая (или плоскость, если все три плоскости одинаковы).

Кривая и поверхность[править | править код]

Аналогично плоскому случаю следующие случаи приводят к нелинейным системам, которые могут быть решены с использованием 1- или 3-мерной итерации Ньютона^[4]:

• параметрическая кривая и

параметрическая поверхность

• параметрическая кривая и

неявная поверхность

Пример:

параметрическая кривая и

неявная поверхность (см. рисунок).

Точки пересечения: (−0.8587, 0.7374, −0.6332), (0.8587, 0.7374, 0.6332).

Пересечение линии и сферы^[en] — это частный случай.

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

Прямая и многогранник[править | править код]

Две поверхности[править | править код]

Две трансверсально пересекающиеся поверхности дают кривую пересечения^[en]. Самый простой случай — линия пересечения двух непараллельных плоскостей.

Примечания[править | править код]

Литература[править | править код]

• Erich Hartmann. Geometry and Algorithms for Computer Aided Design. — Darmstadt University of Technology, 2003.