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

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

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

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

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

На плоскости

Две линии

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

[math]\displaystyle{ a_1x+b_1y=c_1, \ a_2x+b_2y=c_2 }[/math]

можно использовать, например, правило Крамера, или подставляя переменную, координаты точки пересечения [math]\displaystyle{ (x_s,y_s) }[/math]:

[math]\displaystyle{ x_s=\frac{c_1b_2-c_2b_1}{a_1b_2-a_2b_1} , \quad y_s=\frac{a_1c_2-a_2c_1}{a_1b_2-a_2b_1} }[/math].

(Если [math]\displaystyle{ a_1b_2-a_2b_1=0 }[/math], то эти линии параллельны, а это значит, что эти формулы нельзя использовать, так как они предполагают деление на 0.)

Два отрезка

Для двух непараллельных линейных отрезков [math]\displaystyle{ (x_1,y_1),(x_2,y_2) }[/math] и [math]\displaystyle{ (x_3,y_3),(x_4,y_4) }[/math] эта точка не обязательно является точкой пересечения (см. диаграмму), потому что точка пересечения [math]\displaystyle{ (x_0,y_0) }[/math] соответствующих линий не обязательно должна содержаться в линейных отрезках. Для проверки ситуации используются параметрические представления линий:

[math]\displaystyle{ (x(s),y(s))=(x_1+s(x_2-x_1),y_1+s(y_2-y_1)), }[/math]

[math]\displaystyle{ (x(t),y(t))=(x_3+t(x_4-x_3),y_3+t(y_4-y_3)). }[/math]

Отрезки пересекаются только в общей точке [math]\displaystyle{ (x_0,y_0) }[/math] соответствующих линий, если соответствующие параметры [math]\displaystyle{ s_0,t_0 }[/math] удовлетворяют условию [math]\displaystyle{ 0\le s_0,t_0 \le 1 }[/math]. Параметры [math]\displaystyle{ s_0,t_0 }[/math] являются решением линейной системы

[math]\displaystyle{ s(x_2-x_1)-t(x_4-x_3)=x_3-x_1, }[/math]

[math]\displaystyle{ s(y_2-y_1)-t(y_4-y_3)=y_3-y_1 \ . }[/math]

Его можно решить для s и t с помощью правила Крамера (см. выше). Если выполняется условие [math]\displaystyle{ 0\le s_0,t_0 \le 1 }[/math], то вставляется [math]\displaystyle{ s_0 }[/math] или [math]\displaystyle{ t_0 }[/math] в соответствующее параметрическое представление и получается точка пересечения [math]\displaystyle{ (x_0,y_0) }[/math].

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

[math]\displaystyle{ 2s-t=0 }[/math]

[math]\displaystyle{ s+5t=3 }[/math]

и [math]\displaystyle{ s_0=\tfrac{3}{11}, t_0=\tfrac{6}{11} }[/math]. Это означает: линии пересекаются в точке [math]\displaystyle{ (\tfrac{17}{11},\tfrac{14}{11}) }[/math].

Примечание: Рассматривая прямые, а не отрезки, определяемые парами точек, каждое условие [math]\displaystyle{ 0\le s_0,t_0 \le 1 }[/math] может быть опущено, и метод даёт точку пересечения линий (см. выше).

Линия и круг

Для пересечения отрезка [math]\displaystyle{ ax+by=c }[/math] и окружности [math]\displaystyle{ x^2+y^2=r^2 }[/math] решают линейное уравнение для x или y и подставляют в уравнение окружности и получают решение (используя формулу квадратного уравнения) [math]\displaystyle{ (x_1,y_1),(x_2,y_2) }[/math] с:

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

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

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

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

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

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

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

[math]\displaystyle{ (x-x_1)^2+(y-y_1)^2=r_1^2 ,\ \quad (x-x_2)^2+(y-y_2)^2=r_2^2 }[/math]

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

[math]\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. }[/math]

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

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

Особый случай [math]\displaystyle{ \;x_1=y_1=y_2=0 }[/math]; в этом случае начало координат — это центр первого круга, а второй центр лежит на оси абсцисс (см. диаграмму^{[уточнить]}). Уравнение радикальной прямой упрощается до: [math]\displaystyle{ \;2x_2x=r_1^2-r_2^2+x_2^2\; }[/math] а точки пересечения можно записать как [math]\displaystyle{ (x_0,\pm y_0) }[/math] с

[math]\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}\ . }[/math]

В случае [math]\displaystyle{ r_1^2\lt x_0^2 }[/math] окружности не имеют общих точек.
В случае [math]\displaystyle{ r_1^2=x_0^2 }[/math] окружности имеют одну общую точку, а радикальная ось является общей касательной.

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

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

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

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

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

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

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

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

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

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

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

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

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

Если заданы обе кривые явно: [math]\displaystyle{ y=f_1(x), \ y=f_2(x) }[/math], приравнивание их даёт уравнение

[math]\displaystyle{ f_1(x)=f_2(x) \ . }[/math]

Если заданы обе кривые параметрически: [math]\displaystyle{ C_1: (x_1(t),y_1(t)), \ C_2: (x_2(s),y_2(s)). }[/math]

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

[math]\displaystyle{ x_1(t)=x_2(s), \ y_1(t)=y_2(s) \ . }[/math]

Если заданы одна кривая параметрически, а другая неявно: [math]\displaystyle{ C_1: (x_1(t),y_1(t)), \ C_2: f(x,y)=0. }[/math]

Это простейший случай помимо явного. Нужно вставить параметрическое представление [math]\displaystyle{ C_1 }[/math] в уравнение [math]\displaystyle{ f(x,y)=0 }[/math] кривой [math]\displaystyle{ C_2 }[/math], и получится уравнение:

[math]\displaystyle{ f(x_1(t),y_2(t))=0 \ . }[/math]

Если заданы обе кривые неявно: [math]\displaystyle{ C_1: f_1(x,y)=0, \ C_2: f_2(x,y)=0. }[/math]

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

[math]\displaystyle{ f_1(x,y)=0, \ f_2(x,y)=0 \ . }[/math]

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

Примеры:

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

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

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

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

2:[math]\displaystyle{ C_1: f_1(x,y)=x^4+y^4-1=0, }[/math]

[math]\displaystyle{ C_2: f_2(x,y)=(x-0.5)^2+(y-0.5)^2-1=0 }[/math] (см диаграмму).

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

[math]\displaystyle{ {x_{n+1}\choose y_{n+1}}={x_{n}+\delta_x\choose y_n+\delta_y} }[/math] должна быть выполнена, где [math]\displaystyle{ {\delta_x \choose \delta_y} }[/math] является решением линейной системы

[math]\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} }[/math] в точке [math]\displaystyle{ (x_n,y_n) }[/math]. В качестве начальных значений можно выбрать (−0.5, 1) и (1, −0.5).

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ ax(t)+by(t)+cz(t)=d\ , }[/math]

для параметра [math]\displaystyle{ t_0 }[/math] точки пересечения [math]\displaystyle{ (x(t_0),y(t_0),z(t_0)) }[/math].

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

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

Если линия определяется двумя пересекающимися плоскостями [math]\displaystyle{ \varepsilon_i: \ \vec n_i\cdot\vec x=d_i, \ i=1,2 }[/math] и должна пересекаться третьей плоскостью [math]\displaystyle{ \varepsilon_3: \ \vec n_3\cdot\vec x=d_3 }[/math], необходимо оценить общую точку пересечения трёх плоскостей.

Три плоскости [math]\displaystyle{ \varepsilon_i: \ \vec n_i\cdot\vec x=d_i, \ i=1,2,3 }[/math] с линейно независимыми нормальными векторами [math]\displaystyle{ \vec n_1,\vec n_2, \vec n_3 }[/math] имеют точку пересечения

[math]\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)} \ . }[/math]

Для доказательства следует установить [math]\displaystyle{ \vec n_i\cdot\vec p_0=d_i, \ i=1,2,3 , }[/math] используя правила тройного скалярного произведения. Если тройное скалярное произведение равно 0, то плоскости либо не имеют тройного пересечения, либо это прямая (или плоскость, если все три плоскости одинаковы).

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

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

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

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

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

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

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

Пример:

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

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

Точки пересечения: (−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.

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

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

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

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

[1]

[2]

[3]

[4]