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

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

Красная точка представляет собой точку пересечения двух линий

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

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

На плоскости

Подробное рассмотрение темы: Плоскость и Двумерное пространство

Две линии

Основная статья: Пересечение прямых

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

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

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

$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}}}$.

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

Два отрезка

См. также: Задача о пересечении отрезков

Пересечение двух отрезков прямой

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

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

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

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

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

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

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

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

$2s-t=0$

$s+5t=3$

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

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

Пересечение прямой и окружности

Линия и круг

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

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

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

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

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

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

Две окружности

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

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

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

$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}.$

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

Пересечение двух окружностей с центрами на оси абсцисс, их радикальная ось тёмно-красного цвета.

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

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

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

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

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

Пересечение круга и эллипса.

Два конических сечения

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

Две плавные кривые

Трансверсальное пересечение двух кривых.

Касание пересечения (слева), касание (справа).

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

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

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

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

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

Пересечение параметрической и неявной кривых.

Пересечение двух неявных кривых.

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

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

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

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

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

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

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

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

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

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

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

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

Примеры:

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

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

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

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

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

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

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

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

${\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}}$ в точке $(x_{n},y_{n})$. В качестве начальных значений можно выбрать (−0.5, 1) и (1, −0.5).

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

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

Два многоугольника

Пересечение двух многоугольников: метод окон.

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

В пространстве (три измерения)

Подробное рассмотрение темы: Трёхмерное пространство

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

Линия и плоскость

Основная статья: Пересечение прямой и плоскости

Пересечение прямой и плоскости

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

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

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

для параметра $t_{0}$ точки пересечения $(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

Три плоскости

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

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

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

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

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

Пересечение кривой $(t,t^{2},t^{3})$
с поверхностью $x^{4}+y^{4}+z^{4}=1$

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

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

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

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

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

Пример:

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

неявная поверхность $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.