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

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

[[Файл:Schnittpunkt-2g.svg|200px|thumb|Красная точка представляет собой точку пересечения двух линий]]
Задача нахождения пересечения [[Плоскость|плоскостей]] — двумерных линейных геометрических объектов, встроенных в [[Размерность пространства|многомерное пространство]] — сводится к решению [[Система линейных алгебраических уравнений|системы линейных уравнений]].

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

== На плоскости ==
{{подробно|Плоскость|Двумерное пространство}}

=== Две линии ===
{{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.)

=== Два отрезка ===
{{see also|Задача о пересечении отрезков}}
[[Файл:Is-linesegm.svg|300px|thumb|Пересечение двух отрезков прямой]]
Для двух непараллельных [[Отрезок|линейных отрезков]] <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> может быть опущено, и метод даёт точку пересечения линий (см. [[#Две линии|выше]]).

[[Файл:Is-circle-line-s.svg|thumb|Пересечение прямой и окружности]]

=== Линия и круг ===
Для пересечения [[Отрезок|отрезка]] <math>ax+by=c</math> и [[Окружность|окружности]] <math>x^2+y^2=r^2</math> решают линейное уравнение для {{mvar|x}} или {{mvar|y}} и [[Подстановка|подставляют]] в уравнение окружности и получают решение (используя формулу квадратного уравнения) <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|Хартманн|2003|p=17}}, можно рассматривать пересечение прямой и параболы или гиперболы.

=== Две окружности ===
Определение точек пересечения двух окружностей:
: <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>
Эта особая линия является [[Радикальная ось двух окружностей|радикальной осью двух окружностей]].
[[Файл:Is-circle-circle-2x.svg|thumb|upright=1.2|Пересечение двух окружностей с центрами на оси абсцисс, их радикальная ось тёмно-красного цвета.]]

Особый случай <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> окружности не имеют общих точек. <br>
В случае <math>r_1^2=x_0^2</math> окружности имеют одну общую точку, а радикальная ось является общей касательной.

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

Пересечение двух [[круг]]ов (внутренности двух окружностей) образует форму, называемую {{нп5|Линза (геометрия)|линзой||Lens (geometry)}}.
[[Файл:Is-circle-ellipse-s.svg|thumb|Пересечение круга и эллипса.]]

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

=== Две плавные кривые ===
[[Файл:Schnittp2d-transv-s.svg|250px|thumb|Трансверсальное пересечение двух кривых.]]
[[Файл:Beruehr-schnitt-s.svg|350px|thumb|Касание пересечения (слева), касание (справа).]]
Две кривые в <math>\R^2</math> (двумерном пространстве), которые непрерывно дифференцируемы (то есть нет резкого изгиба),
имеют точку пересечения, если они имеют общую точку плоскости и имеют в этой точке
: a: разные касательные ('''[[Трансверсальность|трансверсальное]] пересечение''') или
: b: касательная линия общая, и они пересекают друг друга ('''касание пересечения''', см. диаграмму).

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

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

[[Файл:Schnittp2d-pi-s.svg|thumb|Пересечение параметрической и неявной кривых.]]
[[Файл:Schnittp2d-ii-s.svg|thumb|Пересечение двух неявных кривых.]]
* Если заданы ''обе кривые явно'': <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|t}} или {{mvar|x}} соответственно легко вычислить соответствующую точку. Для неявно заданных кривых эта задача не так проста. В этом случае необходимо определить точку кривой с помощью начальных значений и итерации{{Sfn|Хартманн|2003|p=33}}.

''Примеры:''
: 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)
: 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).

=== Два многоугольника ===
[[Файл:Is-polygpolyg-s.svg|300px|thumb|Пересечение двух многоугольников: метод окон.]]
Если кто-то хочет определить точки пересечения двух [[многоугольник]]ов, можно проверить пересечение любой пары линейных сегментов многоугольников (см. [[#Два отрезка|выше]]). Для многоугольников с большим количеством сегментов этот метод довольно трудоёмок. На практике алгоритм пересечения ускоряется с помощью ''оконных тестов''. В этом случае можно разделить многоугольники на маленькие подполигоны и определить наименьшее окно (прямоугольник со сторонами, параллельными осям координат) для любого подполигона. Перед началом трудоёмкого определения точки пересечения двух отрезков линии любая пара окон проверяется на наличие общих точек{{Sfn|Хартманн|2003|p=79}}

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

=== Линия и плоскость ===
{{main|Пересечение прямой и плоскости}}
[[Файл:Schnittp-ger-eb-s.svg|thumb|Пересечение прямой и плоскости]]
Пересечение прямой и плоскости ''в [[Общее положение|общем положении]]'' в трёх измерениях является точкой.

Обычно линия в пространстве представляется параметрически <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>.

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

{{hider hiding
 |title         = Программный код (Бейсик) для вычисления координат точки пересечения прямой и плоскости
 |content       =

<!-- -->
 <syntaxhighlight lang="basic" line="1">
'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
</syntaxhighlight>
}}

=== Три плоскости ===
Если линия определяется двумя пересекающимися плоскостями <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, то плоскости либо не имеют тройного пересечения, либо это прямая (или плоскость, если все три плоскости одинаковы).

=== Кривая и поверхность ===
[[Файл:Is-pcurve-isurface-s.svg|250px|thumb|Пересечение кривой <math>(t,t^2,t^3)</math> <br>с поверхностью <math>x^4+y^4+z^4=1 </math>]]
Аналогично плоскому случаю следующие случаи приводят к нелинейным системам, которые могут быть решены с использованием 1- или 3-мерной итерации Ньютона{{Sfn|Хартманн|2003|p=93}}:
* параметрическая кривая <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|Пересечение линии и сферы|||Line–sphere intersection}} — это частный случай.

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

=== Прямая и многогранник ===
{{main|Пересечение многогранника и прямой}}

=== Две поверхности ===
{{main|Кривая пересечения}}
Две трансверсально пересекающиеся поверхности дают {{нп5|Кривая пересечения|кривую пересечения||Intersection curve}}. Самый простой случай — линия пересечения двух непараллельных плоскостей.

== Примечания ==
{{примечания}}

== Литература ==
* {{Книга | автор = Erich Hartmann | ссылка = http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf | заглавие = Geometry and Algorithms for Computer Aided Design | издательство = Darmstadt University of Technology | год = 2003 | ref = Хартманн}}

{{rq|style|checktranslate|grammar|tex}}
[[Категория:Вычислительная геометрия]]
[[Категория:Евклидова геометрия]]
[[Категория:Линейная алгебра]]