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

{{Otheruses|Перетин (значення)}}
[[Файл:Schnittpunkt-2g.svg|міні|200x200пкс|Точка перетину двох прямих]]
В [[Геометрія|геометрії]], '''пере́тин'''&nbsp;— це точка, пряма або, більш загально, множина, яка належить двом або більше об'єктам (таким як прямі, криві, площини і поверхні). Найпростіший випадок в [[Евклідова геометрія|евклідовій геометрії]]&nbsp;— це перетин двох різних [[Пряма|прямих]], який може бути однією точкою або [[Порожня множина|порожньою множиною]], коли прямі паралельні, або прямою, якщо прямі збігаються.

Визначення перетину лінійних геометричних об'єктів, впроваджених в [[Розмірність простору|багатомірному]] просторі&nbsp;— це прості задачі [[Лінійна алгебра|лінійної алгебри]], а саме вирішення [[Система лінійних алгебраїчних рівнянь|системи лінійних рівнянь]]. В цілому визначення перетину призводить до [[Нелінійна система|нелінійних рівнянь]], які можуть бути [[Чисельні методи|вирішені чисельно]], наприклад за допомогою [[Метод Ньютона|метода Ньютона]]. Задачи перетину прямої і [[Конічні перетини|конічного перетину]] (кола, еліпсу, параболи і&nbsp;т.&nbsp;д.) або [[Квадріка|квадріки]] (кулі, циліндра, гіперболоїда і&nbsp;т.&nbsp;д.) призводять до [[Квадратне рівняння|квадратних рівнянь]], які можуть бути легко розв'язані. Перетин квадрік призводить до [[Рівняння четвертого степеня|рівнянь четвертого степеня]], які можуть бути розв'язані [[Алгебраїчне рівняння|алгебраїчно]].

== На площині ==
{{further|Площина|Двовимірний простір}}

=== Дві прямі ===
{{Докладніше|Перетин прямих}}
Для визначення точки перетину двох непаралельних прямих

: <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. Тому перетином у випадку паралельних прямих буде або [[порожня множина]], коли прямі не перетинаються, або одна з цих прямих, якщо прямі збігаються.

=== Два відрізки ===
{{Докладніше|Перетин відрізків}}
[[Файл:Is-linesegm.svg|міні|300x300пкс|Перетин двох відрізків]]
Два непаралельні [[Відрізок|відрізки]] <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\leqslant s_0, t_0 \leqslant 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>

Вона може бути розв'язана відносно <math>s</math> та <math>t</math>, якщо використати [[метод Крамера]]. Якщо умова <math>0\leqslant s_0,t_0 \leqslant 1</math> виконана, то підставляючи&nbsp;<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\leqslant s_0,t_0 \leqslant 1</math> може бути видалена, і тоді метод дає точку перетину цих прямих (див. [[Перетин (евклідова геометрія)#Дві_прямі|вище]]).

=== Пряма та коло ===
[[Файл:Is-circle-line-s.svg|міні|Перетин прямої та кола]]
Для перетину

* прямої <math>ax+by=c</math> та [[Коло|кола]] <math>x^2+y^2=r^2</math>

потрібно розв'язати рівняння прямої відносно <math>x</math> або <math>y</math>, підставити його в рівняння кола і розв'язати його як [[Квадратне рівняння|квадратне рівняння]]. Отримаємо <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\geqslant 0</math>. Якщо ця умова виконується зі строгою нерівністю, отримаємо дві точки перетину; в цьому випадку пряма називається [[Січна|січною]] кола, а відрізок, що з'єднує точки перетину називається [[Хорда (геометрія)|хордою]].

Якщо <math>r^2(a^2+b^2)-c^2=0</math>, існує тільки одна точка перетину і [[Дотична пряма до кола|пряма є дотичною до кола]]. Якщо нерівність не виконується, то пряма не перетинається з колом.

Ми припускали, що центр кола збігається з початком координат. Якщо це не так, то потрібно виконати [[паралельне перенесення]]. Більш детально дивитись тут.<ref>Erich Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf ''Geometry and Algorithms for COMPUTER AIDED DESIGN'']. Lecture notes, Technische Universität Darmstadt, October 2003, p. 17</ref>

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

=== Два кола ===
[[Файл:Is-circle-circle-s.svg|міні|Перетин двох кіл]]
[[Файл:Is-circle-ellipse-s.svg|міні|Перетин кола та еліпса]]
Визначення точок перетину двох кіл

* <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>

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

=== Два конічних переріза ===
Проблема перетину еліпса/гіперболи/параболи з іншим [[Конічні перетини|конічним перерізом]] приводить до {{Нп|система поліноміальних рівнянь|системи квадратичних рівнянь||System of polynomial equations}}, яка може бути легко розв'язана для рівнянь в канонічному вигляді за допомогою позбавлення від однієї координати. Властивості конічних перерізів можуть бути використані для пошуку [[Конічні перетини|розв'язку]]. У загальному випадку, точки перетину можуть бути визначені шляхом розв'язку рівняння [[Метод Ньютона|методом Ньютона]]. Якщо а) обидва конічні перерізи задані неявно (за допомогою рівняння), тоді використовується 2-вимірна ітерація метода Ньютона б) один неявно, а інший заданий параметрично, тоді необхідний 1-вимірна ітерація метода Ньютона. Дивіться наступний розділ.

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

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

Якщо обидві криві мають спільну точку&nbsp;{{mvar|S}} та спільну дотичну в ній, але не перетинаються одна з одною, вони просто ''дотикаються'' у точці {{mvar|S}}.

Оскільки дотичні перетини трапляються рідко і з ними складно працювати, тому наступні міркування не враховують цей випадок. Надалі будемо вважати, що виконуються усі потрібні диференціальні умови. Визначення точок перетину завжди призводить до одного або двох нелінійних рівнянь, які можуть бути розв'язані за допомогою метода Ньютона. Можливі такі випадки:
[[Файл:Schnittp2d-pi-s.svg|міні|Перетин параметричної кривої і неявної кривої]]
[[Файл:Schnittp2d-ii-s.svg|міні|Перетин двох неявних кривих]]

* Якщо ''обидві криві явно'' задано: <math>y=f_1(x), \ y=f_2(x)</math>, прирівнюємо їх та отримуємо рівняння

:: <math>f_1(x)=f_2(x) \, .</math>

* Якщо ''обидві криві параметрично'' задані: <math>C_1\colon (x_1(t),y_1(t)), \ C_2\colon (x_2(s),y_2(s)).</math>

: Прирівнюючи їх отримуємо два рівняння з двома змінними:
:: <math>x_1(t)=x_2(s), \ y_1(t)=y_2(s) \, .</math>

* Якщо ''одна крива задана параметрично, а друга&nbsp;— неявно'': <math>C_1\colon (x_1(t),y_1(t)), \ C_2\colon f(x,y)=0.</math>

: Це найпростіший випадок після явного випадку. Потрібно підставити параметричне представлення <math>C_1</math> у рівняння <math>f(x,y)=0</math> кривої <math>C_2</math>, що дасть рівняння:
:: <math>f(x(t),y(t))=0 \, .</math>

* Якщо ''обидві криві неявно'' задано: <math>C_1\colon f_1(x,y)=0, \ C_2\colon f_2(x,y)=0.</math>

: Тут, точки перетину&nbsp;— це рішення системи
:: <math>f_1(x,y)=0, \ f_2(x,y)=0 \, .</math>

Метод Ньютона потребує відповідних початкових значень, які можуть бути отримані шляхом візуалізації обох кривих. Параметрично або неявно задані криві можна легко візуалізовати, адже для будь-якого параметра {{mvar|t}} або {{mvar|x}}, неважко розрахувати відповідні точки. Для неявно заданих кривих це не так просто зробити. У цьому випадку потрібно визначити точку кривої за допомогою початкових значень та ітерації. Див.<ref>Erich Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf ''Geometry and Algorithms for COMPUTER AIDED DESIGN'']. Lecture notes, Technische Universität Darmstadt, October 2003, p. 33</ref>

''Приклади:''

: 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|міні|300x300пкс|Перетин двох багатокутників: метод вікон]]
Якщо потрібно визначити точки перетину двох [[Многокутник|багатокутників]], можна перевірити перетин для кожної пари відрізків цих багатокутників (див. [[Перетин (евклідова геометрія)#Два_відрізки|вище]]). Для багатокутників з багатьох відрізків цей метод є досить повільним, бо він має [[Часова_складність_алгоритму#Поліноміальний_час|квадратичну швидкість]]. На практиці цей алгоритм можна прискорити за допомогою ''метода вікон''. У цьому методі ми ділимо багатокутники на дрібні під-багатокутники і визначаємо мінімальне вікно (прямокутник зі сторонами, паралельними до осей координат) для усіх під-багатокутників. Перед початком дорогих за часом витрат визначення точки перетину двох відрізків, усі пари вікон перевіряються на наявність загальних точок. Детальніше див.<ref>Erich Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdg-skript-1998.pdf ''CDKG: Computerunterstützte Darstellende und Konstruktive Geometrie'']. Lecture notes, TU Darmstadt, 1997, p. 79 (PDF; 3,4&nbsp;MB)</ref>

== У просторі (три вимірний випадок) ==
{{further|Тривимірний простір}}
У 3-вимірному просторі існують точки перетину (спільні точки) кривих і поверхонь. У наступних розділах ми розглянемо тільки&nbsp;''[[Трансверсальність|трансверсальний]] перетин''.

=== Пряма та площина ===
[[Файл:Schnittp-ger-eb-s.svg|міні|Перетин прямої і площини]]
{{Докладніше|Перетин прямої і площини}}
Перетин прямої та площини ''у [[Загальне положення|загальному положенні]]'' в трьохвимірному просторі&nbsp;— це точка.

Зазвичай пряма в просторі задана параметрично <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, то площини або не мають потрійного перетину, коли є пара паралельних площин або перетином буде пряма чи площина, якщо дві або три площини збігаються.

=== Крива та поверхня ===
[[Файл:Is-pcurve-isurface-s.svg|міні|265x265пкс|Перетин кривої <math>(t,t^2,t^3)</math> з поверхнею <math>x^4+y^4+z^4=1</math>]]
Аналогічно до випадку із площинами наступні випадки призводять до нелінійних систем, які можуть бути вирішені з використанням 1- або 3-вимірного [[метод Ньютона|метода Ньютона]].<ref>Erich Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf ''Geometry and Algorithms for COMPUTER AIDED DESIGN'']. Lecture notes, Technische Universität Darmstadt, October 2003, p. 93</ref>

* параметрична крива <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> (див. малюнок).
: Точки перетину: <math>(-0.8587; 0.7374; -0.6332), (0.8587; 0.7374; 0.6332)</math>.

{{Нп|Перетин прямої та сфери|||Line–sphere intersection}}&nbsp;— це окремий простий випадок.

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

=== Прямої і багатогранника ===
{{main|{{Нп|Перетин багатогранника з прямою|||Intersection of a polyhedron with a line}}}}

=== Дві поверхні ===
[[Файл:Is-plane-plane-s.svg|250px|thumb|Перетин двох площин.]]
{{main|{{Нп|Крива перетину|||Intersection curve}}}}
Дві поверхні при [[Трансверсальність|трансверсальному]] перетині задають {{Нп|Крива перетину|криву перетину||Intersection curve}}. Найпростіший випадок лінії перетину&nbsp;— це перетин двох непаралельних площин.

== Див. також ==

* [[Обчислювальна геометрія]]
* [[Лінійне рівняння|Рівняння лінії]]
* [[Перетин прямої і площини]]
* {{Нп|Крива перетину|||Intersection curve}}
* {{Нп|Перетин багатогранника з прямою|||Intersection of a polyhedron with a line}}
* [[Перетин відрізків]]
* [[Перетин прямих]]
* {{Нп|Перетин прямої та сфери|||Line–sphere intersection}}

== Посилання ==
{{примітки}}

== Подальше читання ==
* Nicholas M. Patrikalakis and Takashi Maekawa, ''Shape Interrogation for Computer Aided Design and Manufacturing'', Springer, 2002, {{ISBN|3540424547}}, 9783540424543, pp. 408. [https://books.google.com/books?id=qoxBeti5ySoC&dq=intersection&source=gbs_navlinks_s]

[[Категорія:Обчислювальна геометрія]]
[[Категорія:Евклідова геометрія]]
[[Категорія:Лінійна алгебра]]
[[Категорія:Геометричний перетин]]