Пересечение (геометрия)

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

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

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

В самолете

Две линии

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

$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}>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, их радикальная линия темно-красного цвета.

Особый случай $\;x_{1}=y_{1}=y_{2}=0$ :
В этом случае началом координат является центр первого круга, а второй центр лежит на оси x (см. диаграмму). Уравнение радикальной линии упрощается до $\;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}$ окружности имеют одну общую точку, а радикальная линия является общей касательной.

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

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

Две конические секции

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

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

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

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

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

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

Если обе кривые имеют $точку 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}))$ .

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

Три самолета

Если линия определяется двумя пересекающимися плоскостями $\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).

Пересечение линии и сферы — это простой частный случай.

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

Линия и многогранник

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

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

Сфера и плоскость

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

Пусть S — сфера с центром O , P — плоскость, S. пересекающая Нарисуйте OE перпендикулярно P и встретите P в E. точке Пусть A и B — любые две разные точки пересечения. Тогда AOE и BOE — прямоугольные треугольники с общей стороной OE и гипотенузами AO и BO равными. Следовательно, остальные стороны AE и BE равны. Это доказывает, что все точки пересечения находятся на одинаковом расстоянии от точки E в плоскости P все точки пересечения лежат на окружности C с центром E. , другими словами , ^[5] Это доказывает, что пересечение P и S содержится в C . Обратите внимание, что OE — это ось круга.

рассмотрим точку D окружности C. Теперь Поскольку C лежит в P , то же самое делает D. и С другой стороны, треугольники AOE и DOE — прямоугольные треугольники с общей стороной OE и катетами EA и ED равными. Следовательно, гипотенузы AO и DO равны и равны радиусу S так что D лежит в S. , Это доказывает, что содержится в пересечении P и S. C

Как следствие, на сфере существует ровно одна окружность, которую можно провести через три заданные точки. ^[6]

Доказательство можно расширить, чтобы показать, что все точки окружности находятся на общем угловом расстоянии от одного из ее полюсов. ^[7]

Сравните также конические сечения , из которых можно получить овалы .

Две сферы

Чтобы показать, что нетривиальное пересечение двух сфер представляет собой круг, предположим (без ограничения общности), что одна сфера (с радиусом $R$ ) центрируется в начале координат. Точки на этой сфере удовлетворяют

x^{2}+y^{2}+z^{2}=R^{2}.

Также без ограничения общности предположим, что вторая сфера радиусом $r$ , центрируется в точке на положительной оси X на расстоянии $a$ от происхождения. Его пункты удовлетворяют

(x-a)^{2}+y^{2}+z^{2}=r^{2}.

Пересечение сфер — это набор точек, удовлетворяющих обоим уравнениям. Вычитание уравнений дает

{\begin{aligned}(x-a)^{2}-x^{2}&=r^{2}-R^{2}\\a^{2}-2ax&=r^{2}-R^{2}\\x&={\frac {a^{2}+R^{2}-r^{2}}{2a}}.\end{aligned}}

В единственном случае $a=0$ , сферы концентричны. Есть две возможности: если $R=r$ , сферы совпадают, а пересечение — вся сфера; если $R\not =r$ , сферы не пересекаются и пересечение пусто.Когда a не равно нулю, пересечение лежит в вертикальной плоскости с этой координатой x, которая может пересекать обе сферы, быть касательной к обеим сферам или быть внешней по отношению к обеим сферам.Результат следует из предыдущего доказательства для пересечений сферы и плоскости.

См. также

Примечания

^ Эрих Хартманн: Геометрия и алгоритмы компьютерного проектирования . Конспект лекций, Технический университет Дармштадта, октябрь 2003 г., с. 17
^ Эрих Хартманн: Геометрия и алгоритмы компьютерного проектирования . Конспект лекций, Технический университет Дармштадта, октябрь 2003 г., с. 33
^ Эрих Хартманн: CDKG: Компьютерная начертательная и конструктивная геометрия . Конспект лекций, ТУ Дармштадта, 1997, с. 79 (PDF; 3,4 МБ)
^ Эрих Хартманн: Геометрия и алгоритмы компьютерного проектирования . Конспект лекций, Технический университет Дармштадта, октябрь 2003 г., с. 93
^ Доказательство следует за Хоббсом, предложение 304.
^ Хоббс, предложение 308.
^ Хоббс, предложение 310.

Ссылки

Хоббс, Калифорния (1921). Твердая геометрия . Г.Х. Кент. стр. 397 и далее.

Дальнейшее чтение

Хейнс, Эрик (6 июня 2021 г.). «Пересечения (страница ресурсов по трассировке лучей)» . Рендеринг в реальном времени . Проверено 14 декабря 2023 г. сетка процедур пересечения различных популярных объектов, указывающая на ресурсы в книгах и в Интернете.
Николас М. Патрикалакис и Такаши Маекава, «Опрос формы для автоматизированного проектирования и производства» , Springer, 2002 г., ISBN 3540424547 , 9783540424543, стр. 408. [1]
Сайкс, М.; Комсток, CE (1922). Твердая геометрия . Рэнд МакНелли. стр. 81 и далее.

[1] Эрих Хартманн: Геометрия и алгоритмы компьютерного проектирования . Конспект лекций, Технический университет Дармштадта, октябрь 2003 г., с. 17

[2] Эрих Хартманн: Геометрия и алгоритмы компьютерного проектирования . Конспект лекций, Технический университет Дармштадта, октябрь 2003 г., с. 33

[3] Эрих Хартманн: CDKG: Компьютерная начертательная и конструктивная геометрия . Конспект лекций, ТУ Дармштадта, 1997, с. 79 (PDF; 3,4 МБ)

[4] Эрих Хартманн: Геометрия и алгоритмы компьютерного проектирования . Конспект лекций, Технический университет Дармштадта, октябрь 2003 г., с. 93

[5] Доказательство следует за Хоббсом, предложение 304.

[6] Хоббс, предложение 308.

[7] Хоббс, предложение 310.

[1]

[2]

[3]

[4]

[5]

[6]

[7]