Пересечение (евклидова геометрия)

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

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

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

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

${\displaystyle a_{1}x+b_{1}y=c_{1},\ a_{2}x+b_{2}y=c_{2}}$

можно использовать, например, правило Крамера, или подставляя переменную, координаты точки пересечения ${\displaystyle (x_{s},y_{s})}$:

${\displaystyle x_{s}={\frac {c_{1}b_{2}-c_{2}b_{1}}{a_{1}b_{2}-a_{2}b_{1}}},\quad y_{s}={\frac {a_{1}c_{2}-a_{2}c_{1}}{a_{1}b_{2}-a_{2}b_{1}}}}$.

(Если ${\displaystyle a_{1}b_{2}-a_{2}b_{1}=0}$, то эти линии параллельны, а это значит, что эти формулы нельзя использовать, так как они предполагают деление на 0.)

Для двух непараллельных линейных отрезков ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$ и ${\displaystyle (x_{3},y_{3}),(x_{4},y_{4})}$ эта точка не обязательно является точкой пересечения (см. диаграмму), потому что точка пересечения ${\displaystyle (x_{0},y_{0})}$ соответствующих линий не обязательно должна содержаться в линейных отрезках. Для проверки ситуации используются параметрические представления линий:

${\displaystyle (x(s),y(s))=(x_{1}+s(x_{2}-x_{1}),y_{1}+s(y_{2}-y_{1})),}$

${\displaystyle (x(t),y(t))=(x_{3}+t(x_{4}-x_{3}),y_{3}+t(y_{4}-y_{3})).}$

Отрезки пересекаются только в общей точке ${\displaystyle (x_{0},y_{0})}$ соответствующих линий, если соответствующие параметры ${\displaystyle s_{0},t_{0}}$ удовлетворяют условию ${\displaystyle 0\leq s_{0},t_{0}\leq 1}$. Параметры ${\displaystyle s_{0},t_{0}}$ являются решением линейной системы

${\displaystyle s(x_{2}-x_{1})-t(x_{4}-x_{3})=x_{3}-x_{1},}$

${\displaystyle s(y_{2}-y_{1})-t(y_{4}-y_{3})=y_{3}-y_{1}\ .}$

Его можно решить для s и t с помощью правила Крамера (см. выше). Если выполняется условие ${\displaystyle 0\leq s_{0},t_{0}\leq 1}$, то вставляется ${\displaystyle s_{0}}$ или ${\displaystyle t_{0}}$ в соответствующее параметрическое представление и получается точка пересечения ${\displaystyle (x_{0},y_{0})}$.

Пример: Для отрезков ${\displaystyle (1,1),(3,2)}$ и ${\displaystyle (1,4),(2,-1)}$ получается линейная система

${\displaystyle 2s-t=0}$

${\displaystyle s+5t=3}$

и ${\displaystyle s_{0}={\tfrac {3}{11}},t_{0}={\tfrac {6}{11}}}$. Это означает: линии пересекаются в точке ${\displaystyle ({\tfrac {17}{11}},{\tfrac {14}{11}})}$.

Примечание: Рассматривая прямые, а не отрезки, определяемые парами точек, каждое условие ${\displaystyle 0\leq s_{0},t_{0}\leq 1}$ может быть опущено, и метод даёт точку пересечения линий (см. выше).

Для пересечения отрезка ${\displaystyle ax+by=c}$ и окружности ${\displaystyle x^{2}+y^{2}=r^{2}}$ решают линейное уравнение для x или y и подставляют в уравнение окружности и получают решение (используя формулу квадратного уравнения) ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$ с:

${\displaystyle x_{1/2}={\frac {ac\pm b{\sqrt {r^{2}(a^{2}+b^{2})-c^{2}}}}{a^{2}+b^{2}}}}$,

${\displaystyle y_{1/2}={\frac {bc\mp a{\sqrt {r^{2}(a^{2}+b^{2})-c^{2}}}}{a^{2}+b^{2}}}}$,

если ${\displaystyle r^{2}(a^{2}+b^{2})-c^{2}\geq 0}$. Если это условие выполняется со строгим неравенством, то существуют две точки пересечения; в этом случае прямая называется секущей линией окружности, а отрезок прямой, соединяющий точки пересечения, называется хордой окружности.

Если выполняется ${\displaystyle r^{2}(a^{2}+b^{2})-c^{2}=0}$, то существует только одна точка пересечения и прямая касается окружности. Если слабое неравенство не выполняется, линия не пересекает окружность.

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

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

${\displaystyle (x-x_{1})^{2}+(y-y_{1})^{2}=r_{1}^{2},\ \quad (x-x_{2})^{2}+(y-y_{2})^{2}=r_{2}^{2}}$

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

${\displaystyle 2(x_{2}-x_{1})x+2(y_{2}-y_{1})y=r_{1}^{2}-x_{1}^{2}-y_{1}^{2}-r_{2}^{2}+x_{2}^{2}+y_{2}^{2}.}$

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

Особый случай ${\displaystyle \;x_{1}=y_{1}=y_{2}=0}$; в этом случае начало координат — это центр первого круга, а второй центр лежит на оси абсцисс (см. диаграмму^[]). Уравнение радикальной прямой упрощается до: ${\displaystyle \;2x_{2}x=r_{1}^{2}-r_{2}^{2}+x_{2}^{2}\;}$ а точки пересечения можно записать как ${\displaystyle (x_{0},\pm y_{0})}$ с

${\displaystyle x_{0}={\frac {r_{1}^{2}-r_{2}^{2}+x_{2}^{2}}{2x_{2}}},\quad y_{0}={\sqrt {r_{1}^{2}-x_{0}^{2}}}\ .}$

В случае ${\displaystyle r_{1}^{2}<x_{0}^{2}}$ окружности не имеют общих точек.
В случае ${\displaystyle r_{1}^{2}=x_{0}^{2}}$ окружности имеют одну общую точку, а радикальная ось является общей касательной.

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

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

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

Две кривые в ${\displaystyle \mathbb {R} ^{2}}$ (двумерном пространстве), которые непрерывно дифференцируемы (то есть нет резкого изгиба), имеют точку пересечения, если они имеют общую точку плоскости и имеют в этой точке

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

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

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

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

• Если заданы обе кривые явно: ${\displaystyle y=f_{1}(x),\ y=f_{2}(x)}$, приравнивание их даёт уравнение

${\displaystyle f_{1}(x)=f_{2}(x)\ .}$

• Если заданы обе кривые параметрически: ${\displaystyle C_{1}:(x_{1}(t),y_{1}(t)),\ C_{2}:(x_{2}(s),y_{2}(s)).}$

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

${\displaystyle x_{1}(t)=x_{2}(s),\ y_{1}(t)=y_{2}(s)\ .}$

• Если заданы одна кривая параметрически, а другая неявно: ${\displaystyle C_{1}:(x_{1}(t),y_{1}(t)),\ C_{2}:f(x,y)=0.}$

Это простейший случай помимо явного. Нужно вставить параметрическое представление ${\displaystyle C_{1}}$ в уравнение ${\displaystyle f(x,y)=0}$ кривой ${\displaystyle C_{2}}$, и получится уравнение:

${\displaystyle f(x_{1}(t),y_{2}(t))=0\ .}$

• Если заданы обе кривые неявно: ${\displaystyle C_{1}:f_{1}(x,y)=0,\ C_{2}:f_{2}(x,y)=0.}$

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

${\displaystyle f_{1}(x,y)=0,\ f_{2}(x,y)=0\ .}$

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

Примеры:

1: ${\displaystyle C_{1}:(t,t^{3})}$ и окружность ${\displaystyle C_{2}:(x-1)^{2}+(y-1)^{2}-10=0}$ (см диаграмму).

Итерация Ньютона ${\displaystyle t_{n+1}:=t_{n}-{\frac {f(t_{n})}{f'(t_{n})}}}$ для функции

${\displaystyle f(t)=(t-1)^{2}+(t^{3}-1)^{2}-10}$ должна быть выполнена. В качестве начальных значений можно выбрать −1 и 1.5.

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

2:${\displaystyle C_{1}:f_{1}(x,y)=x^{4}+y^{4}-1=0,}$

${\displaystyle C_{2}:f_{2}(x,y)=(x-0.5)^{2}+(y-0.5)^{2}-1=0}$ (см диаграмму).

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

${\displaystyle {x_{n+1} \choose y_{n+1}}={x_{n}+\delta _{x} \choose y_{n}+\delta _{y}}}$ должна быть выполнена, где ${\displaystyle {\delta _{x} \choose \delta _{y}}}$ является решением линейной системы

${\displaystyle {\begin{pmatrix}{\frac {\partial f_{1}}{\partial x}}&{\frac {\partial f_{1}}{\partial y}}\\{\frac {\partial f_{2}}{\partial x}}&{\frac {\partial f_{2}}{\partial y}}\end{pmatrix}}{\delta _{x} \choose \delta _{y}}={-f_{1} \choose -f_{2}}}$ в точке ${\displaystyle (x_{n},y_{n})}$. В качестве начальных значений можно выбрать (−0.5, 1) и (1, −0.5).

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

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

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

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

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

Обычно линия в пространстве представляется параметрически ${\displaystyle (x(t),y(t),z(t))}$, а плоскость — уравнением ${\displaystyle ax+by+cz=d}$. Вставка представления параметра в уравнение даёт линейное уравнение

${\displaystyle ax(t)+by(t)+cz(t)=d\ ,}$

для параметра ${\displaystyle t_{0}}$ точки пересечения ${\displaystyle (x(t_{0}),y(t_{0}),z(t_{0}))}$.

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

'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

Если линия определяется двумя пересекающимися плоскостями ${\displaystyle \varepsilon _{i}:\ {\vec {n}}_{i}\cdot {\vec {x}}=d_{i},\ i=1,2}$ и должна пересекаться третьей плоскостью ${\displaystyle \varepsilon _{3}:\ {\vec {n}}_{3}\cdot {\vec {x}}=d_{3}}$, необходимо оценить общую точку пересечения трёх плоскостей.

Три плоскости ${\displaystyle \varepsilon _{i}:\ {\vec {n}}_{i}\cdot {\vec {x}}=d_{i},\ i=1,2,3}$ с линейно независимыми нормальными векторами ${\displaystyle {\vec {n}}_{1},{\vec {n}}_{2},{\vec {n}}_{3}}$ имеют точку пересечения

${\displaystyle {\vec {p}}_{0}={\frac {d_{1}({\vec {n}}_{2}\times {\vec {n}}_{3})+d_{2}({\vec {n}}_{3}\times {\vec {n}}_{1})+d_{3}({\vec {n}}_{1}\times {\vec {n}}_{2})}{{\vec {n}}_{1}\cdot ({\vec {n}}_{2}\times {\vec {n}}_{3})}}\ .}$

Для доказательства следует установить ${\displaystyle {\vec {n}}_{i}\cdot {\vec {p}}_{0}=d_{i},\ i=1,2,3,}$ используя правила тройного скалярного произведения. Если тройное скалярное произведение равно 0, то плоскости либо не имеют тройного пересечения, либо это прямая (или плоскость, если все три плоскости одинаковы).

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

• параметрическая кривая ${\displaystyle C:(x(t),y(t),z(t))}$ и

параметрическая поверхность ${\displaystyle S:(x(u,v),y(u,v),z(u,v))\ ,}$

• параметрическая кривая ${\displaystyle C:(x(t),y(t),z(t))}$ и

неявная поверхность ${\displaystyle S:f(x,y,z)=0\ .}$

Пример:

параметрическая кривая ${\displaystyle C:(t,t^{2},t^{3})}$ и

неявная поверхность ${\displaystyle S:x^{4}+y^{4}+z^{4}-1=0}$ (см. рисунок).

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

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

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

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

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