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

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

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

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

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

На плоскости править

Две линии править

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

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$ , то существует только одна точка пересечения и прямая касается окружности. Если слабое неравенство не выполняется, линия не пересекает окружность.

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

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

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

(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}$ окружности имеют одну общую точку, а радикальная ось является общей касательной.

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

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

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

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

Задача пересечения эллипса, гиперболы, параболы с другим коническим сечением сводится к системе квадратных уравнений, которую в частных случаях легко решить, исключив одну координату. Специальные свойства конических сечений могут быть использованы для получения решения. В общем, точки пересечения могут быть определены путём решения уравнения с помощью итерации Ньютона. Если а) обе коники заданы неявно (посредством уравнения), необходима двумерная итерация Ньютона; б) одна неявно, а другая параметрически — необходимо, чтобы была задана 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 соответственно легко вычислить соответствующую точку. Для неявно заданных кривых эта задача не так проста. В этом случае необходимо определить точку кривой с помощью начальных значений и итерации^[2].

Примеры:

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).

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

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

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

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

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

Линия и плоскость править

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

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

Обычно линия в пространстве представляется параметрически $(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-мерной итерации Ньютона^[4]:

параметрическая кривая $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).

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

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

Прямая и многогранник править

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

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

Литература править

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

[_de7ee612a3bf7461-1] Хартманн, 2003, p. 17.

[_de7ee412a3bf70c3-2] Хартманн, 2003, p. 33.

[_de7ee812a3bf7785-3] Хартманн, 2003, p. 79.

[_de7eee12a3bf81dd-4] Хартманн, 2003, p. 93.

[1]

[2]

[3]

[4]