Материал: 252_337
Мал. 146
Однак отриманої залежності замало для остаточного виснов ку про те, що задані відрізки перетинаються. Така сама ситу ація повинна мати місце і для відрізка з кінцями р3 і р 4 : якщо дивитимемося із точки р3 у точку Рі, то при переведенні погля ду в точки р1 їр2 поворот здійснюватиметься у різні боки. Від повідно до цього умову виконання такого взаємного розміщен ня відрізків запишемо так:
[(Р4 ~Ра) х (Рі -Р8 )] * [0>4 ~Рз) х (Р2 -МУ\ < °- А тепер вже можна сформулювати остаточний висновок.
Два задані відрізки з кінцями у точках pvp2 ір3,р4 перети наються тільки в разі, коли виконуються такі дві умови:
[(р2 -Рі) * (р8 ~Рі>) • [(?2 - Р і ) х о>4 -Рі)] < °;
Ш -Ря) х (Рі -Р8 )1 • [СР4 -Рв) х (Ра - Рз)1 < °- Зрозуміло, що якщо два задані відрізки не перетинаються
(мал. 146, б), то одна із зазначених вище умов не виконується. Цікавими для аналізу є інші випадки взаємного розміщення двох заданих відрізків і умови їх визначення, які ми далі й роз
глянемо.
На малюнку 146, в представлено випадок, коли кінець одно го відрізка розміщений на іншому відрізку. Як бачимо, умова
[(Р2 ~Рі) х (Рз ~Рі)3 • Е(Рг ~Рі) х (Р4 ~Рі)} < ° виконується, однак якщо дивитися із точки р3 у точку р4, а потім у точку р2, то (Р4 - Рз) х (Р2 _ Рз) = ®' Таким чином, друга із зазначених вище умов у даному разі буде такою:
[(Р4 -Р») х (Рі "Рз)] * [(Р4 "Рз> х (Р2 _ Рз)] = °-
Якщо лише один із виразів (Pj-pt) х (pk ~Pt) дорівнює 0, де і, І - кінці одного відрізка, k - один із кінців іншого, то це означає, що кінець k одного відрізка лежить усередині другого відрізка.
Розглянемо випадок, коли по одному з кінців кожного з двох заданих відрізків збігаються. Саме така ситуація зображена на ма люнку 146, г. Зрозуміло, що у такому разі у кожному з виразів [(Р2 - Рі) х (Рз - Рі)] * [(Р2 - Рі) х (Р4 " Рі)] і
[(Р4 - Р 8 ) х (Рі "Рз)1 • [(Р4 "Рз) х (Рг "Рз)] лише один із множників набуває значення 0.
9 Інформатика, 9-10 о. |
257 |
Якщо (pj -pt) x (pk -Pi)=0i (pl -pk) x (Pi -pj = 0, де і, j та h,l- кінці одного відрізка, k та і - один із кінців іншого, то це
означає, що кінці двох заданих відрізків k та і збігаються.
Окремо розглянемо випадки, зображені на малюнках 146, діє. Для них усі вирази (ру. - pt) х (pk - pt) дорівнюють 0. Однак відмінність між ними суттєва: на малюнку 146, д відрізки не тільки перетинаються, а ще й накладаються, а на малюнку 146, є взагалі не мають спільних точок. Як розрізнити ці дві ситуації, якщо аналіз значень виразів [(р2 -р^) х (р3 -p-J] • [(р2 -рг ) х (р4 -pj)]
і [(Р4 ~Рз) * ІРі -Рзїї - [(^4 ~Рз> х (Рг _ Рз)] не Да є вагомих резуль татів?
На малюнках, що розглядаються, вже є підказка: необхідно розглянути прямокутники мінімальної площі, що вміщують у собі задані відрізки. Якщо ці прямокутники перетинаються, то і відрізки мають спільні точки, тобто накладаються. Для пе ревірки цієї умови достатньо мати інформацію про координати кінців цих відрізків. Але перш ніж записати необхідну умову,
треба ввести деякі нові позначення. |
|
|
|
|
||||
|
|
|
Нехай |
х\ |
- |
тіп{х^, |
х2), |
|
( * і! |
Уі). |
х'2 |
= тах(хх; |
х2), |
у\ |
= тіпіу^, |
у2), |
|
у'2 |
= тах{ух; у2) (мал. 147). Тоді |
|||||||
|
|
|||||||
|
|
умовою перетину двох прямокут |
||||||
|
|
ників мінімальної |
площі, |
що |
||||
|
:.;!:і |
-Лх^Уг) вміщують дві задані прямі, |
буде |
|||||
|
|
така: |
|
|
|
|
||
|
|
Мал. 147 |
(Х'2 >= Х'3) and (х'4 |
>= х'Л and |
||||
|
|
|
(y'2>=y'3)and(y'i>=y\). |
|
||||
|
Саме ця умова виконується для відрізків, зображених на ма |
|||||||
люнку 146, д, і не виконується для відрізків на малюнку 146, є. Підіб'ємо остаточний підсумок усіх наведених міркувань. 1. Якщо задача вимагає визначення, чи перетинаються за
дані два відрізки в одній точці, яка одночасно не є жодним з їхніх кінців, то достатньо перевірити такі дві умови:
[(Р2 -Рі) х (Рг " P i ) ! • КРа ~Рд х Щ ~Рд) < °! [ІРІ -Р3) х (Рі -Рз)1 * [(Р4 ~Рз) х (Рг ~Рз)1 < °-
2. Якщо в задачі можливий перетин відрізків з накладан ням їхніх кінців (мал. 146, в, г), то необхідно провести деталь ніший аналіз щодо нульових значень виразів (р -pt) х (pk - pt)- 3. Якщо у сформульованій задачі ставиться запитання про визначення наявності спільних точок (не обов'язково однієї) для двох заданих відрізків, то спочатку достатньо перевірити виконан ня умови (х'2 >= х'3) and (х'4 >= х\) and (у'2 >= у'3) and (у\ >= у\).
У разі її невиконання можна зразу давати негативну відповідь. У випадку позитивної відповіді і для того, щоб виключити варіант, зображений на малюнку 146, б, необхідно перевірити ще виконання умов:
258
[(p2 -Pi) x (p3 -РіУ\ • [(P2 -Pi)x (P4 -Pi)l * o; [(P4 - Ps> X (Pi - РЗ>] • f(P4 - Рз) X (P2 - Рз)] * °-
Наведемо приклад фрагмента Pascal-програми, що аналізує перетин двох заданих відрізків:
X 1 := min(p[1].x, р[2].х); х_2 := тах(р[1].х, р[2].х); {Обчислення координат}
у_1 |
:= min(p[1].y, р[2].у); у_2 |
:= тах(р[1].у, р[2].у); |
{вершин охоплюючих} |
х_3 |
:= тіп(р[3].х, р[4].х); х_4 |
:= тах(р[3].х, р[4].х); |
{прямокутників.} |
у_3 := min(p[3].y, р[4].у); у_4 := тах(р[3].у, р[4].у); |
|
||
|
{Перевірка умови перетину охоплюючих прямокутників.} |
||
if (х_2 >= х_3) and (х_4 >= х_1) and (у_2 >= у_3) and (у_4 >= у_1) {Якщо вони} then {перетинаються, то обчислення параметрів для перевірки умови їх перетину.}
begin
р_1_23:=(р[2].х-р[1].хГ(р[3].у-р[1].у)(р[3].х-р[1].хГ(р[2].у-р[1].у); р_1_24:=(р[2].х-р[1].хГ(р[4].у-р[1].у)(р[4].х-р[1].хПр[2].у-р[1].у); Р_3_41:=(р[4].х-р[3].х)*(р[1].у-р[3].у)(р[1].х-р[3].х)*(р[4].у-р[3].у); р_3_42 := (р[4].х- р[3].хГ(р[2].у- р[3].у) (р[2].х- р[3].х)*(р[4].у- р[3].у); if (PJ_23 * р_1_24 <= 0) and (р_3_41 * р_3_42 <= 0) {Перевіркаумови}
then writeln(f_out, 'Yes crossing') |
{перетину відрізків.} |
else writeln(f out, 'Not crossing'); |
|
end |
|
else writeln(f_out, 'Not crossing'); |
|
Поставлену на початку задачу про визначення факту пере тину двох заданих відрізків можна було б розв'язувати інакше. Для цього за основу слід взяти розв'язання системи двох ліній них рівнянь, що описують прямі, яким відповідають задані відрізки. Наведемо послідовність відповідних дій.
1.Визначити коефіцієнти загальних рівнянь прямих av bv
с1 і а2, Ь2, с2, яким належать задані відрізки, враховуючи коор
динати їх кінців.
2. Розв'язати систему лінійних рівнянь
{a1x + bly + cl =0; \а2х + Ь2у + с2=0
і визначити, чи існує її розв'язок (х; у). Аналіз отриманого розв'язку дасть відповідь на запитання: чи існує єдиний розв'язок або ж таких розв'язків безліч?
3. Якщо існує єдиний розв'язок досліджуваної системи лінійних рівнянь {х; у), то залишається перевірити, чи нале жить ця точка обом відрізкам:
(х\ <= х) and (х <= х'2) and (у\ <= у) and (у <= у'2) and (х'3 <= х) and (х <= х\) and (у'3 <= у) and (у <= у\).
4. У разі, коли система двох рівнянь має безліч розв'язків, це означає, що досліджувані відрізки можуть мати спільні точ ки. Тому для отримання позитивної відповіді на поставлене у
9* |
259 |
сформульованій задачі запитання щодо перетину двох заданих відрізків доцільною є перевірка виконання додаткової умови:
(х'2 >= х'3) and (х\ >= х\) and (у'2 >= у'3) and {у\ >= у\).
Як видно з другого алгоритму визначення перетину двох за даних відрізків координатами своїх кінців, необхідно викону вати велику кількість арифметичних дій. По-перше, це робить алгоритм досить громіздким, по-друге, вимагає більше часу на його виконання. Якщо в задачі необхідно дослідити лише два задані відрізки, то, можливо, такий підхід і не є дуже обтяжли вим. Однак у разі, коли дослідження відбувається для значно більшої кількості відрізків, то перевага першого алгоритму не заперечна: у ньому виконуються лише арифметичні дії відні мання та множення і логічні дії порівняння. Відсутність ділен ня значно збільшує ймовірність отримання коректного резуль тату.
Саме в цьому ми матимемо змогу переконатися у наступних алгоритмах, що розглядатимуться.
Визначення положення точки відносно багатокутника
Розглянемо багатокутник на площині, заданий координата ми своїх вершин у порядку їх обходу, та деяку довільну точку (X; Y) (мал. 148). Нас цікавитиме питання, чи належить ця точка заданому багатокутнику.
У |
(х2; |
у2) |
|
У |
|
(*0І Уг) |
|
|
|
|
|
|
|||
|
|
|
х3; у3) |
|
|
|
|
|
to; Уі) (х4; у І) |
|
|
|
fe; yd |
(*?; |
у3) |
|
|
|
|
|
|
||
(0;0^ |
|
|
х |
(0; 0) |
|
|
х |
|
а) |
|
|
|
|
б) |
|
|
|
|
Мал. 148 |
|
|
|
|
Поставлену задачу можна розв'язувати традиційним шля хом: з'єднати точку (X; Y) з кожною із вершин заданого багато кутника, знайти суму площ отриманих трикутників і порівня ти з площею всього багатокутника, алгоритм обчислення зна чення якої вже відомий. Однак, як видно з двох варіантів багатокутників, зображених на малюнку 148, лише для опук лого багатокутника такий алгоритм дасть правильну відповідь (мал. 148, а). У випадку неопуклого багатокутника (мал. 148, б) такий підхід не дасть коректного результату.
260
Підійдемо до розв'язання нашої задачі з дещо іншого боку. Побу дуємо відрізок, який паралельний осі Ох, одним із кінців якого є точка (X; Y), а другим - точка (х'; У), де х' > max(xv х2,..., хп). На ма люнку 124 зображено два варіанти багатокутників та різні розмі щення точки (X; Y) відносно них. Згідно з побудовою відрізків з кінцями (X; Y) і (х'; Y), точка (х'; Y) завжди знаходиться поза межа ми внутрішньої частини багатокутника. А це означає, що для того, аби із точки (X; Y) потрапити у точку (х'; Y), рухаючись цим відріз ком, треба перетинати сторони заданого багатокутника, якщо вони з'являються на цьому шляху. Як видно з малюнків 149, якщо точ ка (X; Y) належить внутрішній частині багатокутника, то таких пе ретинів буде непарна кількість (мал. 149, а, б), якщо ж зовнішній, - то парна (мал. 149, г) або перетини зовсім відсутні (мал. 149, в).
в) |
г) |
Мал. 149
Чи не стане перешкодою випадок, коли побудований відрізок проходитиме через вершини заданого багатокутника? Розглянемо відповідні приклади, зображені на малюнку 150.
На малюнку 150, а точка (X; У) розташована всередині зада ного багатокутника і перетин відрізка з кінцями у точках (X; Y) і (х'; Y) відбувається у вершині (х3; у3). Хоча вершина (х3; у3) на лежить двом сторонам багатокутника, у цьому разі логічно вра хувати лише один перетин. Такий висновок збігається з раніше визначеною ознакою належності заданої точки багатокутнику: кількість перетинів непарна.
Для багатокутника, зображеного на малюнку 150, б, задана точка (X; Y) знаходиться зовні і проходить через його сторони
261