Русская Википедия:Пересечение (евклидова геометрия)
Пересечение в евклидовой геометрии — точка или кривая, общие для двух или более объектов (таких как кривые, плоскости и поверхности). Простейший случай — пересечение двух различных прямых на плоскости, которое либо является одной точкой, либо не существует, если прямые параллельные.
Задача нахождения пересечения плоскостей — двумерных линейных геометрических объектов, встроенных в многомерное пространство — сводится к решению системы линейных уравнений.
В общем случае, пересечение определяется системой нелинейных уравнений, которая може быть решена численно, например, с использованием метода Ньютона. Задачи о пересечении прямой и конического сечения (круг, эллипс, парабола и т. д. ) или квадрики (сфера, цилиндр, гиперболоид и т. д. ) приводят к квадратным уравнениям, которые легко решаются. Пересечения между квадриками приводят к уравнениям четвёртой степени, которые можно решить алгебраически.
На плоскости
Две линии
Шаблон:Main Для определения точки пересечения двух непараллельных прямых:
- <math>a_1x+b_1y=c_1, \ a_2x+b_2y=c_2 </math>
можно использовать, например, правило Крамера, или подставляя переменную, координаты точки пересечения <math>(x_s,y_s)</math>:
- <math> 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> a_1b_2-a_2b_1=0</math>, то эти линии параллельны, а это значит, что эти формулы нельзя использовать, так как они предполагают деление на 0.)
Два отрезка
Для двух непараллельных линейных отрезков <math>(x_1,y_1),(x_2,y_2)</math> и <math>(x_3,y_3),(x_4,y_4)</math> эта точка не обязательно является точкой пересечения (см. диаграмму), потому что точка пересечения <math>(x_0,y_0)</math> соответствующих линий не обязательно должна содержаться в линейных отрезках. Для проверки ситуации используются параметрические представления линий:
- <math> (x(s),y(s))=(x_1+s(x_2-x_1),y_1+s(y_2-y_1)),</math>
- <math> (x(t),y(t))=(x_3+t(x_4-x_3),y_3+t(y_4-y_3)). </math>
Отрезки пересекаются только в общей точке <math>(x_0,y_0)</math> соответствующих линий, если соответствующие параметры <math>s_0,t_0</math> удовлетворяют условию <math> 0\le s_0,t_0 \le 1 </math>. Параметры <math>s_0,t_0 </math> являются решением линейной системы
- <math>s(x_2-x_1)-t(x_4-x_3)=x_3-x_1,</math>
- <math> s(y_2-y_1)-t(y_4-y_3)=y_3-y_1 \ .</math>
Его можно решить для s и t с помощью правила Крамера (см. выше). Если выполняется условие <math> 0\le s_0,t_0 \le 1 </math>, то вставляется <math>s_0</math> или <math>t_0</math> в соответствующее параметрическое представление и получается точка пересечения <math>(x_0,y_0)</math>.
Пример: Для отрезков <math>(1,1),(3,2)</math> и <math>(1,4),(2,-1)</math> получается линейная система
- <math> 2s-t=0</math>
- <math>s+5t=3</math>
и <math>s_0=\tfrac{3}{11}, t_0=\tfrac{6}{11}</math>. Это означает: линии пересекаются в точке <math>(\tfrac{17}{11},\tfrac{14}{11})</math>.
Примечание: Рассматривая прямые, а не отрезки, определяемые парами точек, каждое условие <math> 0\le s_0,t_0 \le 1 </math> может быть опущено, и метод даёт точку пересечения линий (см. выше).
Линия и круг
Для пересечения отрезка <math>ax+by=c</math> и окружности <math>x^2+y^2=r^2</math> решают линейное уравнение для Шаблон:Mvar или Шаблон:Mvar и подставляют в уравнение окружности и получают решение (используя формулу квадратного уравнения) <math>(x_1,y_1),(x_2,y_2)</math> с:
- <math>x_{1/2}= \frac{ac\pm b\sqrt{r^2(a^2+b^2)-c^2}}{a^2+b^2}</math>,
- <math>y_{1/2}= \frac{bc\mp a\sqrt{r^2(a^2+b^2)-c^2}}{a^2+b^2}</math>,
если <math> r^2(a^2+b^2)-c^2\ge 0</math>. Если это условие выполняется со строгим неравенством, то существуют две точки пересечения; в этом случае прямая называется секущей линией окружности, а отрезок прямой, соединяющий точки пересечения, называется хордой окружности.
Если выполняется <math> r^2(a^2+b^2)-c^2=0 </math>, то существует только одна точка пересечения и прямая касается окружности. Если слабое неравенство не выполняется, линия не пересекает окружность.
Если середина круга не является началом координатШаблон:Sfn, можно рассматривать пересечение прямой и параболы или гиперболы.
Две окружности
Определение точек пересечения двух окружностей:
- <math>(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>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>\;x_1=y_1=y_2=0 </math>; в этом случае начало координат — это центр первого круга, а второй центр лежит на оси абсцисс (см. диаграммуШаблон:Уточнить). Уравнение радикальной прямой упрощается до: <math>\;2x_2x=r_1^2-r_2^2+x_2^2\;</math> а точки пересечения можно записать как <math>(x_0,\pm y_0)</math> с
- <math>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>r_1^2<x_0^2</math> окружности не имеют общих точек.
В случае <math>r_1^2=x_0^2</math> окружности имеют одну общую точку, а радикальная ось является общей касательной.
Любой общий случай, как написано выше, можно превратить сдвигом и поворотом в частный случай.
Пересечение двух кругов (внутренности двух окружностей) образует форму, называемую Шаблон:Нп5.
Два конических сечения
Задача пересечения эллипса, гиперболы, параболы с другим коническим сечением сводится к системе квадратных уравнений, которую в частных случаях легко решить, исключив одну координату. Специальные свойства конических сечений могут быть использованы для получения решения. В общем, точки пересечения могут быть определены путём решения уравнения с помощью итерации Ньютона. Если а) обе коники заданы неявно (посредством уравнения), необходима двумерная итерация Ньютона; б) одна неявно, а другая параметрически — необходимо, чтобы была задана 1-мерная итерация Ньютона.
Две плавные кривые
Две кривые в <math>\R^2</math> (двумерном пространстве), которые непрерывно дифференцируемы (то есть нет резкого изгиба), имеют точку пересечения, если они имеют общую точку плоскости и имеют в этой точке
- a: разные касательные (трансверсальное пересечение) или
- b: касательная линия общая, и они пересекают друг друга (касание пересечения, см. диаграмму).
Если обе кривые имеют общую точку Шаблон:Mvar и касательную, но не пересекают друг друга, они просто «касаются» в точке Шаблон:Mvar.
Поскольку касания пересечений возникают редко и с ними трудно справиться, следующие соображения не учитывают этот случай. В любом случае ниже предполагаются все необходимые дифференциальные условия. Определение точек пересечения всегда приводит к одному или двум нелинейным уравнениям, которые можно решить с помощью итерации Ньютона. Список возникающих случаев следующий:
- Если заданы обе кривые явно: <math> y=f_1(x), \ y=f_2(x)</math>, приравнивание их даёт уравнение
- <math>f_1(x)=f_2(x) \ .</math>
- Если заданы обе кривые параметрически: <math>C_1: (x_1(t),y_1(t)), \ C_2: (x_2(s),y_2(s)).</math>
- Приравнивая их, получаем два уравнения с двумя переменными:
- <math>x_1(t)=x_2(s), \ y_1(t)=y_2(s) \ .</math>
- Если заданы одна кривая параметрически, а другая неявно: <math>C_1: (x_1(t),y_1(t)), \ C_2: f(x,y)=0.</math>
- Это простейший случай помимо явного. Нужно вставить параметрическое представление <math>C_1</math> в уравнение <math>f(x,y)=0</math> кривой <math>C_2</math>, и получится уравнение:
- <math>f(x_1(t),y_2(t))=0 \ .</math>
- Если заданы обе кривые неявно: <math>C_1: f_1(x,y)=0, \ C_2: f_2(x,y)=0.</math>
- Здесь точка пересечения — это решение системы
- <math>f_1(x,y)=0, \ f_2(x,y)=0 \ .</math>
Любая итерация Ньютона требует удобных начальных значений, которые можно получить, визуализировав обе кривые. Параметрически или явно заданная кривая может быть легко визуализирована, потому что для любого параметра Шаблон:Mvar или Шаблон:Mvar соответственно легко вычислить соответствующую точку. Для неявно заданных кривых эта задача не так проста. В этом случае необходимо определить точку кривой с помощью начальных значений и итерацииШаблон:Sfn.
Примеры:
- 1: <math>C_1: (t,t^3)</math> и окружность <math>C_2: (x-1)^2+(y-1)^2-10=0</math> (см диаграмму).
- Итерация Ньютона <math>t_{n+1}:=t_n-\frac{f(t_n)}{f'(t_n)}</math> для функции
- <math>f(t)=(t-1)^2+(t^3-1)^2-10</math> должна быть выполнена. В качестве начальных значений можно выбрать −1 и 1.5.
- Точки пересечения: (−1.1073, −1.3578), (1.6011, 4.1046)
- Итерация Ньютона <math>t_{n+1}:=t_n-\frac{f(t_n)}{f'(t_n)}</math> для функции
- 2:<math>C_1: f_1(x,y)=x^4+y^4-1=0,</math>
- <math>C_2: f_2(x,y)=(x-0.5)^2+(y-0.5)^2-1=0 </math> (см диаграмму).
- Итерация Ньютона
- <math>{x_{n+1}\choose y_{n+1}}={x_{n}+\delta_x\choose y_n+\delta_y}</math> должна быть выполнена, где <math>{\delta_x \choose \delta_y}</math> является решением линейной системы
- <math>\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>(x_n,y_n)</math>. В качестве начальных значений можно выбрать (−0.5, 1) и (1, −0.5).
- Линейная система может быть решена по правилу Крамера.
- Точками пересечения являются (−0.3686, 0.9953) и (0.9953, −0.3686).
Два многоугольника
Если кто-то хочет определить точки пересечения двух многоугольников, можно проверить пересечение любой пары линейных сегментов многоугольников (см. выше). Для многоугольников с большим количеством сегментов этот метод довольно трудоёмок. На практике алгоритм пересечения ускоряется с помощью оконных тестов. В этом случае можно разделить многоугольники на маленькие подполигоны и определить наименьшее окно (прямоугольник со сторонами, параллельными осям координат) для любого подполигона. Перед началом трудоёмкого определения точки пересечения двух отрезков линии любая пара окон проверяется на наличие общих точекШаблон:Sfn
В пространстве (три измерения)
Шаблон:Further В трёхмерном пространстве есть точки пересечения (общие точки) между кривыми и поверхностями. В следующих разделах мы рассматриваем только трансверсальное пересечение.
Линия и плоскость
Пересечение прямой и плоскости в общем положении в трёх измерениях является точкой.
Обычно линия в пространстве представляется параметрически <math> (x(t),y(t),z(t)) </math>, а плоскость — уравнением <math>ax+by+cz=d</math>. Вставка представления параметра в уравнение даёт линейное уравнение
- <math>ax(t)+by(t)+cz(t)=d\ ,</math>
для параметра <math>t_0</math> точки пересечения <math>(x(t_0),y(t_0),z(t_0))</math>.
Если линейное уравнение не имеет решения, либо прямая лежит на плоскости, либо параллельна ей.
Три плоскости
Если линия определяется двумя пересекающимися плоскостями <math>\varepsilon_i: \ \vec n_i\cdot\vec x=d_i, \ i=1,2</math> и должна пересекаться третьей плоскостью <math>\varepsilon_3: \ \vec n_3\cdot\vec x=d_3 </math>, необходимо оценить общую точку пересечения трёх плоскостей.
Три плоскости <math>\varepsilon_i: \ \vec n_i\cdot\vec x=d_i, \ i=1,2,3 </math> с линейно независимыми нормальными векторами <math> \vec n_1,\vec n_2, \vec n_3</math> имеют точку пересечения
- <math> \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>\vec n_i\cdot\vec p_0=d_i, \ i=1,2,3 , </math> используя правила тройного скалярного произведения. Если тройное скалярное произведение равно 0, то плоскости либо не имеют тройного пересечения, либо это прямая (или плоскость, если все три плоскости одинаковы).
Кривая и поверхность
с поверхностью <math>x^4+y^4+z^4=1 </math>
Аналогично плоскому случаю следующие случаи приводят к нелинейным системам, которые могут быть решены с использованием 1- или 3-мерной итерации НьютонаШаблон:Sfn:
- параметрическая кривая <math>C: (x(t),y(t),z(t)) </math> и
- параметрическая поверхность <math>S: (x(u,v),y(u,v),z(u,v))\ ,</math>
- параметрическая кривая <math>C: (x(t),y(t),z(t)) </math> и
- неявная поверхность <math> S: f(x,y,z)=0\ .</math>
Пример:
- параметрическая кривая <math>C: (t,t^2,t^3)</math> и
- неявная поверхность <math>S: x^4+y^4+z^4-1=0</math> (см. рисунок).
- Точки пересечения: (−0.8587, 0.7374, −0.6332), (0.8587, 0.7374, 0.6332).
Шаблон:Нп5 — это частный случай.
Как и в случае линии и плоскости, пересечение кривой и поверхности в общем положении состоит из дискретных точек, но кривая может частично или полностью содержаться на поверхности.
Прямая и многогранник
Две поверхности
Шаблон:Main Две трансверсально пересекающиеся поверхности дают Шаблон:Нп5. Самый простой случай — линия пересечения двух непараллельных плоскостей.
Примечания
Литература
