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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Точка перетину двох прямих

В геометрії, пере́тин — це точка, пряма або, більш загально, множина, яка належить двом або більше об'єктам (таким як прямі, криві, площини і поверхні). Найпростіший випадок в евклідовій геометрії — це перетин двох різних прямих, який може бути однією точкою або порожньою множиною, коли прямі паралельні, або прямою, якщо прямі збігаються.

Визначення перетину лінійних геометричних об'єктів, впроваджених в багатомірному просторі — це прості задачі лінійної алгебри, а саме вирішення системи лінійних рівнянь. В цілому визначення перетину призводить до нелінійних рівнянь, які можуть бути вирішені чисельно, наприклад за допомогою метода Ньютона. Задачи перетину прямої і конічного перетину (кола, еліпсу, параболи і т. д.) або квадріки (кулі, циліндра, гіперболоїда і т. д.) призводять до квадратних рівнянь, які можуть бути легко розв'язані. Перетин квадрік призводить до рівнянь четвертого степеня, які можуть бути розв'язані алгебраїчно.

На площині[ред. | ред. код]

Помилка Lua у Модуль:Further у рядку 31: attempt to call field 'formatPages' (a nil value).

Дві прямі[ред. | ред. код]

Докладніше: Перетин прямих

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

За методом Крамера або за допомогою підстановки змінної, отримуємо координати точки перетину :

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

Два відрізки[ред. | ред. код]

Докладніше: Перетин відрізків
Перетин двох відрізків

Два непаралельні відрізки та не обов'язково перетинаються (див. малюнок), тому що точка перетину відповідних прямих не обов'язково потрапить саме на відрізки, а не на їх продовження. Для перевіки цієї ситуації використовують параметричне представлення прямих:

Відрізки перетинаються тільки в одній точці , якщо відповідні параметри відповідають умові . Параметри є розв'язком лінійної системи

Вона може бути розв'язана відносно та , якщо використати метод Крамера. Якщо умова виконана, то підставляючи  або у відповідне параметричне рівняння можна отримати точку перетину .

Наприклад: для відрізків  і отримуємо лінійну систему

З якої випливає . Що означає: лінії перетинаються в точці .

Зауваження: розглядаючи прямі, замість відрізків, визначені парами точок, кожна умова може бути видалена, і тоді метод дає точку перетину цих прямих (див. вище).

Пряма та коло[ред. | ред. код]

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

Для перетину

  • прямої та кола 

потрібно розв'язати рівняння прямої відносно  або , підставити його в рівняння кола і розв'язати його як квадратне рівняння. Отримаємо  з

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

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

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

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

Два кола[ред. | ред. код]

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

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

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

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

Два конічних переріза[ред. | ред. код]

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

Дві гладкі криві[ред. | ред. код]

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

Дві криві в (двовимірний простір), які є безперервно дифференційованими (тобто не мають різкого вигину), мають точки перетину, якщо вони мають спільну точку площини і у цій точці:

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

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

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

Перетин параметричної кривої і неявної кривої
Перетин двох неявних кривих
  • Якщо обидві криві явно задано: , прирівнюємо їх та отримуємо рівняння
  • Якщо обидві криві параметрично задані:
Прирівнюючи їх отримуємо два рівняння з двома змінними:
  • Якщо одна крива задана параметрично, а друга — неявно:
Це найпростіший випадок після явного випадку. Потрібно підставити параметричне представлення у рівняння  кривої , що дасть рівняння:
  • Якщо обидві криві неявно задано:
Тут, точки перетину — це рішення системи

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

Приклади:

1: та коло  (див. малюнок).
Потрібно застосувати метод Ньютона  для функції
. Як початкові значення можна взяти −1 та 1.5.
Отримаємо точки перетину: (−1.1073, −1.3578), (1.6011, 4.1046).
2:
(див. малюнок).
, де  є розв'язком лінійної системи
у точці . Як початкові значення можна взяти (−0.5; 1) та (1; −0.5).
Лінійну систему можна розв'язати за допомогою правила Крамера.
Точки перетину: (−0.3686; 0.9953) та (0.9953; −0.3686).

Два багатокутники[ред. | ред. код]

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

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

У просторі (три вимірний випадок)[ред. | ред. код]

Помилка Lua у Модуль:Further у рядку 31: attempt to call field 'formatPages' (a nil value). У 3-вимірному просторі існують точки перетину (спільні точки) кривих і поверхонь. У наступних розділах ми розглянемо тільки трансверсальний перетин.

Пряма та площина[ред. | ред. код]

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

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

Зазвичай пряма в просторі задана параметрично , а площина задана загальним рівнянням . Для пошуку точки перетину підставимо координати точки у рівняння:

для параметра координати точки перетину будуть .

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

Три площини[ред. | ред. код]

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

Три площини  з лінійно незалежними векторами нормалей  мають точку перетину

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

Крива та поверхня[ред. | ред. код]

Перетин кривої з поверхнею 

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

  • параметрична крива та: параметрична поверхня 
  • параметрична крива та: неявна поверхня 

Приклад:

параметрична крива та: неявна поверхня (див. малюнок).
Точки перетину: .

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

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

Прямої і багатогранника[ред. | ред. код]

Дві поверхні[ред. | ред. код]

Перетин двох площин.
Докладніше: Крива перетину[en]

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

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]

  1. Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN. Lecture notes, Technische Universität Darmstadt, October 2003, p. 17
  2. Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN. Lecture notes, Technische Universität Darmstadt, October 2003, p. 33
  3. Erich Hartmann: CDKG: Computerunterstützte Darstellende und Konstruktive Geometrie. Lecture notes, TU Darmstadt, 1997, p. 79 (PDF; 3,4 MB)
  4. Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN. Lecture notes, Technische Universität Darmstadt, October 2003, p. 93

Подальше читання[ред. | ред. код]

  • Nicholas M. Patrikalakis and Takashi Maekawa, Shape Interrogation for Computer Aided Design and Manufacturing, Springer, 2002, ISBN 3540424547, 9783540424543, pp. 408. [1]