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

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

${\displaystyle a_{1}x+b_{1}y=c_{1},\ a_{2}x+b_{2}y=c_{2}}$

За методом Крамера або за допомогою підстановки змінної, отримуємо координати точки перетину ${\displaystyle (x_{s},y_{s})}$:

${\displaystyle 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}}}.\ }$

Якщо прямі паралельні, то ${\displaystyle a_{1}b_{2}-a_{2}b_{1}=0}$ і ці формули не можуть бути використані, тому що вони включають ділення на 0. Тому перетином у випадку паралельних прямих буде або порожня множина, коли прямі не перетинаються, або одна з цих прямих, якщо прямі збігаються.

Перетин двох відрізків

Два непаралельні відрізки ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$ та ${\displaystyle (x_{3},y_{3}),(x_{4},y_{4})}$ не обов'язково перетинаються (див. малюнок), тому що точка перетину ${\displaystyle (x_{0},y_{0})}$ відповідних прямих не обов'язково потрапить саме на відрізки, а не на їх продовження. Для перевіки цієї ситуації використовують параметричне представлення прямих:

${\displaystyle (x(s),y(s))=(x_{1}+s(x_{2}-x_{1}),y_{1}+s(y_{2}-y_{1})),}$

${\displaystyle (x(t),y(t))=(x_{3}+t(x_{4}-x_{3}),y_{3}+t(y_{4}-y_{3})).}$

Відрізки перетинаються тільки в одній точці ${\displaystyle (x_{0},y_{0})}$, якщо відповідні параметри ${\displaystyle s_{0},t_{0}}$ відповідають умові ${\displaystyle 0\leqslant s_{0},t_{0}\leqslant 1}$. Параметри ${\displaystyle s_{0},t_{0}}$ є розв'язком лінійної системи

${\displaystyle s(x_{2}-x_{1})-t(x_{4}-x_{3})=x_{3}-x_{1},}$

${\displaystyle s(y_{2}-y_{1})-t(y_{4}-y_{3})=y_{3}-y_{1}\ .}$

Вона може бути розв'язана відносно ${\displaystyle s}$ та ${\displaystyle t}$, якщо використати метод Крамера. Якщо умова ${\displaystyle 0\leqslant s_{0},t_{0}\leqslant 1}$ виконана, то підставляючи ${\displaystyle s_{0}}$ або ${\displaystyle t_{0}}$ у відповідне параметричне рівняння можна отримати точку перетину ${\displaystyle (x_{0},y_{0})}$.

Наприклад: для відрізків ${\displaystyle (1,1),(3,2)}$ і ${\displaystyle (1,4),(2,-1)}$ отримуємо лінійну систему

${\displaystyle 2s-t=0}$

${\displaystyle s+5t=3}$

З якої випливає ${\displaystyle s_{0}={\tfrac {3}{11}},t_{0}={\tfrac {6}{11}}}$. Що означає: лінії перетинаються в точці ${\displaystyle ({\tfrac {17}{11}},{\tfrac {14}{11}})}$.

Зауваження: розглядаючи прямі, замість відрізків, визначені парами точок, кожна умова ${\displaystyle 0\leqslant s_{0},t_{0}\leqslant 1}$ може бути видалена, і тоді метод дає точку перетину цих прямих (див. вище).

Перетин прямої та кола

Для перетину

• прямої ${\displaystyle ax+by=c}$ та кола ${\displaystyle x^{2}+y^{2}=r^{2}}$

потрібно розв'язати рівняння прямої відносно ${\displaystyle x}$ або ${\displaystyle y}$, підставити його в рівняння кола і розв'язати його як квадратне рівняння. Отримаємо ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$ з

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

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

для ${\displaystyle r^{2}(a^{2}+b^{2})-c^{2}\geqslant 0}$. Якщо ця умова виконується зі строгою нерівністю, отримаємо дві точки перетину; в цьому випадку пряма називається січною кола, а відрізок, що з'єднує точки перетину називається хордою.

Якщо ${\displaystyle r^{2}(a^{2}+b^{2})-c^{2}=0}$, існує тільки одна точка перетину і пряма є дотичною до кола. Якщо нерівність не виконується, то пряма не перетинається з колом.

Ми припускали, що центр кола збігається з початком координат. Якщо це не так, то потрібно виконати паралельне перенесення. Більш детально дивитись тут.[1]

Перетин прямої і параболи або гіперболи можна розглядати аналогічно.

Перетин двох кіл

Перетин кола та еліпса

Визначення точок перетину двох кіл

• ${\displaystyle (x-x_{1})^{2}+(y-y_{1})^{2}=r_{1}^{2},\ \quad (x-x_{2})^{2}+(y-y_{2})^{2}=r_{2}^{2}}$

можна звести до попереднього випадку перетину лінії і кола шляхом віднімання двох заданих рівнянь виходить лінійне рівняння:

${\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}.}$

Перетин двох кругів утворює форму, звану лінзою.

Проблема перетину еліпса/гіперболи/параболи з іншим конічним перерізом приводить до системи квадратичних рівнянь, яка може бути легко розв'язана для рівнянь в канонічному вигляді за допомогою позбавлення від однієї координати. Властивості конічних перерізів можуть бути використані для пошуку розв'язку. У загальному випадку, точки перетину можуть бути визначені шляхом розв'язку рівняння методом Ньютона. Якщо а) обидва конічні перерізи задані неявно (за допомогою рівняння), тоді використовується 2-вимірна ітерація метода Ньютона б) один неявно, а інший заданий параметрично, тоді необхідний 1-вимірна ітерація метода Ньютона. Дивіться наступний розділ.

Трансверсальний перетин двох кривих

Дотичний перетин (ліворуч), дотикаються (праворуч)

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

a: мають різні дотичній прямі (трансверсальний перетин), або:

б: дотичні лінії збігаються, і лінії перетинаються одна з одною (дотичний перетин, див. малюнок).

Якщо обидві криві мають спільну точку S та спільну дотичну в ній, але не перетинаються одна з одною, вони просто дотикаються у точці S.

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

Перетин параметричної кривої і неявної кривої

Перетин двох неявних кривих

• Якщо обидві криві явно задано: ${\displaystyle y=f_{1}(x),\ y=f_{2}(x)}$, прирівнюємо їх та отримуємо рівняння

${\displaystyle f_{1}(x)=f_{2}(x)\,.}$

• Якщо обидві криві параметрично задані: ${\displaystyle C_{1}\colon (x_{1}(t),y_{1}(t)),\ C_{2}\colon (x_{2}(s),y_{2}(s)).}$

Прирівнюючи їх отримуємо два рівняння з двома змінними:

${\displaystyle x_{1}(t)=x_{2}(s),\ y_{1}(t)=y_{2}(s)\,.}$

• Якщо одна крива задана параметрично, а друга — неявно: ${\displaystyle C_{1}\colon (x_{1}(t),y_{1}(t)),\ C_{2}\colon f(x,y)=0.}$

Це найпростіший випадок після явного випадку. Потрібно підставити параметричне представлення ${\displaystyle C_{1}}$ у рівняння ${\displaystyle f(x,y)=0}$ кривої ${\displaystyle C_{2}}$, що дасть рівняння:

${\displaystyle f(x(t),y(t))=0\,.}$

• Якщо обидві криві неявно задано: ${\displaystyle C_{1}\colon f_{1}(x,y)=0,\ C_{2}\colon f_{2}(x,y)=0.}$

Тут, точки перетину — це рішення системи

${\displaystyle f_{1}(x,y)=0,\ f_{2}(x,y)=0\,.}$

Метод Ньютона потребує відповідних початкових значень, які можуть бути отримані шляхом візуалізації обох кривих. Параметрично або неявно задані криві можна легко візуалізовати, адже для будь-якого параметра t або x, неважко розрахувати відповідні точки. Для неявно заданих кривих це не так просто зробити. У цьому випадку потрібно визначити точку кривої за допомогою початкових значень та ітерації. Див.[2]

Приклади:

1: ${\displaystyle C_{1}:(t,t^{3})}$ та коло ${\displaystyle C_{2}:(x-1)^{2}+(y-1)^{2}-10=0}$ (див. малюнок).

Потрібно застосувати метод Ньютона ${\displaystyle t_{n+1}:=t_{n}-{\frac {f(t_{n})}{f'(t_{n})}}}$ для функції

${\displaystyle f(t)=(t-1)^{2}+(t^{3}-1)^{2}-10}$. Як початкові значення можна взяти −1 та 1.5.

Отримаємо точки перетину: (−1.1073, −1.3578), (1.6011, 4.1046).

2: ${\displaystyle C_{1}:f_{1}(x,y)=x^{4}+y^{4}-1=0,}$

${\displaystyle C_{2}:f_{2}(x,y)=(x-0.5)^{2}+(y-0.5)^{2}-1=0}$ (див. малюнок).

${\displaystyle {x_{n+1} \choose y_{n+1}}={x_{n}+\delta _{x} \choose y_{n}+\delta _{y}}}$, де ${\displaystyle {\delta _{x} \choose \delta _{y}}}$ є розв'язком лінійної системи

${\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}}}$ у точці ${\displaystyle (x_{n},y_{n})}$. Як початкові значення можна взяти (−0.5; 1) та (1; −0.5).

Лінійну систему можна розв'язати за допомогою правила Крамера.

Точки перетину: (−0.3686; 0.9953) та (0.9953; −0.3686).

Перетин двох багатокутників: метод вікон

Якщо потрібно визначити точки перетину двох багатокутників, можна перевірити перетин для кожної пари відрізків цих багатокутників (див. вище). Для багатокутників з багатьох відрізків цей метод є досить повільним, бо він має квадратичну швидкість. На практиці цей алгоритм можна прискорити за допомогою метода вікон. У цьому методі ми ділимо багатокутники на дрібні під-багатокутники і визначаємо мінімальне вікно (прямокутник зі сторонами, паралельними до осей координат) для усіх під-багатокутників. Перед початком дорогих за часом витрат визначення точки перетину двох відрізків, усі пари вікон перевіряються на наявність загальних точок. Детальніше див.[3]

Перетин прямої і площини

Перетин прямої та площини у загальному положенні в трьохвимірному просторі — це точка.

Зазвичай пряма в просторі задана параметрично ${\displaystyle (x(t),y(t),z(t))}$, а площина задана загальним рівнянням ${\displaystyle ax+by+cz=d}$. Для пошуку точки перетину підставимо координати точки у рівняння:

${\displaystyle ax(t)+by(t)+cz(t)=d\,,}$

для параметра ${\displaystyle t_{0}}$ координати точки перетину будуть ${\displaystyle (x(t_{0}),y(t_{0}),z(t_{0}))}$.

Якщо лінійне рівняння не має розв'язку, то пряма або лежить на площині або паралельна їй.

Якщо пряма задана двома площинами, що перетинаються ${\displaystyle \varepsilon _{i}:\ {\vec {n}}_{i}\cdot {\vec {x}}=d_{i},\ i=1,2}$ і її потрібно перетнути із третьою площиною ${\displaystyle \varepsilon _{3}:\ {\vec {n}}_{3}\cdot {\vec {x}}=d_{3}}$, знайдемо точку перетину усіх трьох площин.

Три площини ${\displaystyle \varepsilon _{i}:\ {\vec {n}}_{i}\cdot {\vec {x}}=d_{i},\ i=1,2,3}$ з лінійно незалежними векторами нормалей ${\displaystyle {\vec {n}}_{1},{\vec {n}}_{2},{\vec {n}}_{3}}$ мають точку перетину

${\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})}}\ .}$

Для доказу слід встановити, що ${\displaystyle {\vec {n}}_{i}\cdot {\vec {p}}_{0}=d_{i},\ i=1,2,3,}$ використовуючи правила мішаного добутку. Якщо мішаний добуток дорівнює 0, то площини або не мають потрійного перетину, коли є пара паралельних площин або перетином буде пряма чи площина, якщо дві або три площини збігаються.

Перетин кривої ${\displaystyle (t,t^{2},t^{3})}$ з поверхнею ${\displaystyle x^{4}+y^{4}+z^{4}=1}$

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

• параметрична крива ${\displaystyle C:(x(t),y(t),z(t))}$ та: параметрична поверхня ${\displaystyle S:(x(u,v),y(u,v),z(u,v))\,,}$

• параметрична крива ${\displaystyle C:(x(t),y(t),z(t))}$ та: неявна поверхня ${\displaystyle S:f(x,y,z)=0\,.}$

Приклад:

параметрична крива ${\displaystyle C:(t,t^{2},t^{3})}$ та: неявна поверхня ${\displaystyle S:x^{4}+y^{4}+z^{4}-1=0}$ (див. малюнок).

Точки перетину: ${\displaystyle (-0.8587;0.7374;-0.6332),(0.8587;0.7374;0.6332)}$.

Перетин прямої та сфери — це окремий простий випадок.

Як і у випадку прямої і площини, перетин кривої і поверхні в загальному положенні складається з дискретних точок, але крива може бути частково або повністю розташована на поверхні.

Перетин двох площин.

Дві поверхні при трансверсальному перетині задають криву перетину. Найпростіший випадок лінії перетину — це перетин двох непаралельних площин.