Материал: 252_337

if flag or Odd(count) {Точка належить багатокутнику, коли вона збігається з однією}

then writeln(f_OUt, 'Yes') {із вершин або кількість перетинів ребер непарна.}

else writeln(f_out,'No');

Оскільки для визначення положення точки відносно задано­ го n-кутника необхідно порахувати кількість перетинів побудо­ ваного горизонтального відрізка з його сторонами, то оцінка ефективності роботи такого алгоритму буде лінійною і станови­ тиме О(га).

Для тестування алгоритму необхідно переглянути всі мож­ ливі випадки розташування точки на площині відносно задано­ го своїми вершинами n-кутника: точка усередині багатокутни­ ка; точка ззовні багатокутника, але побудований відрізок прямої перетинає багатокутник; точка ззовні багатокутника і відрізок не перетинає його.

Щодо вигляду самого багатокутника, то обов'язковим є не тільки задання багатокутників як з невеликою кількістю вер­ шин, наприклад до 10, так і з достатньо великою, наприклад близько 100.

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

Для отримання максимальної результативності виконання тестування побудованого алгоритму щодо визначення розмі­ щення точки відносно заданого багатокутника всі зазначені вище параметри рекомендується комбінувати у різноманітних варіантах.

Побудова опуклої оболонки

Під опуклою оболонкою розу­ міють опуклий багатокутник міні­ мальної площі, який містить у собі всі задані точки на площині. Зро­ зуміло, що вершинами такого ба­ гатокутника можуть бути лише де­ які точки із множини заданих, а всі решта заданих точок лежатимуть у середині побудованого багатокут­ ника (мал. 152).

Побудову опуклої оболонки можна наочно уявити собі наступним чином. Нехай на плоску дошку, що відіграє роль площини, набито багато цвяхів, що є заданими точками. Наки­ немо на цвяхи мотузку таким чином, щоб усі їх охопити, і поч-

267

немо її стягувати, зав'язуючи у вузол. Врешті-решт наша мо­ тузка охопить усі цвяхи, зачепившись за деякі з них, і утво­ рить опуклу оболонку.

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

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

Це далеко не кращий алгоритм щодо часу його виконання. Його можна визначити як повноперебірний. Оцінку ефектив­ ності цього алгоритму можна визначити так. На кроці побудо­ ви прямих для визначених пар точок оцінка ефективності ста­ новить 0(п2). Однак для кожної такої прямої необхідно пере­ глянути решту точок для визначення їхнього розміщення на площині відносно цієї прямої, що становить 0(гі). Таким чи­ ном, загальна оцінка запропонованого алгоритму буде 0(п3).

Далі розглянемо більш ефективні методи розв'язання побу­ дови опуклої оболонки.

Метод додавання точок

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

Саме тому почнемо перегляд з неї. Далі розглядатимемо точки у порядку зростання значень їх абсцис. Саме за цією ознакою на малюнку 153 визначена послідовність точок р^,р2^Р^Рі'

Якщо переглядати точки згідно з послідовністю їх задання, то спочатку будуть з'єднані точки р1 ір2, потім р2 ір3, і наоста-

268

нокрд» РІ- Отримана ламана не буде опуклою оболонкою, у ній зайвими є два відрізки, позначені на малюнку 153 пунктиром. Вірною побудовою буде з'єднання відрізками точок рх, р3, р4 . Як визначити коректність побудови цієї ламаної? Із точки р1 спостерігатимемо за переміщенням із точки р2 у точку р3. При цьому буде виконано лівий поворот, тобто поворот проти годин­ никової стрілки. Запам'ятаємо цей факт.

Далі перейдемо у точку р2 і з неї спостерігатимемо за пе­ реміщенням із точки р3 у точку р4. Тепер буде здійснено правий поворот, тобто поворот за годинниковою стрілкою. Отже, пору­ шена ознака незмінного повороту при обході опуклою оболон­ кою: оскільки ми виконуємо обхід за годинниковою стрілкою, то повинні весь час робити правий поворот. Якщо вилучити із перегляду точку р2, то, спостерігаючи із точкир1 за переміщен­ ням із точки р3 У точку j?4, зафіксуємо правий поворот.

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

Найпростіше усі точки поточного стану опуклої оболонки запи­ сувати у стек. Першим елементом стеку завжди буде точкар1 упо­ рядкованої послідовності всіх заданих точок. На і-му кроці з точ­ ки рі дивитимемося у точки рі+1 і рі+2. Якщо матиме місце вираз

(Рі+і ~ РІ) * (Р/+2 - Рд = (ХІ+І - ХІЩ+І - У І) ~ (ХІ+2 - *ЩІг ~ У І) % °» т о

це означатиме, що виконано правий поворот проти годинни­ кової стрілки і точка рі + 1є претендентом на вершину опуклої оболонки та повинна бути занесена до вершини стеку.

А як бути у протилежному ви­ падку, якщо точка рі+1 до стеку не заноситься? Розглянемо малюнок 154. На перших двох кроках у стек буде занесено точки рх, р2, р3. Для точки р4 умова належності опуклій оболонці не виконується, і вона не потрапляє до стеку.

Але з малюнка 154 видно, що і точки р2, р3 також необхідно виключити. Для цього треба

дослідити верхній елемент стеку, у нашому випадку це точкар3 . Якщо і для пари точок р3 ірь не виконується необхідна умова, то стек зменшується на один елемент шляхом виключення з нього точки, що знаходиться у його вершині, тобто р3. Така послідовність дій продовжується до тих пір, поки не знайдеться у вершині стеку точка, для якої разом із точкою рь необхідна умова виконається. Тоді точка р5 занесеться у стек і для нашого прикладу поточний вміст стеку буде таким: pvp5. До речі, відки­ нуті точки р2, р3, р4 будуть брати участь у наступному перегляді, коли будуватиметься нижня частина опуклої оболонки.

269

Наскільки ефективним є даний алгоритм? Найперше по­ мітне те, що при побудові опуклої оболонки всі точки розгляда­ ються максимум двічі: перший раз, коли будується верхня час­ тина опуклої оболонки, а другий раз - нижня. По-друге, для визначення напряму повороту виконується мінімальна кількість арифметичних операцій.

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

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

Таким чином, застосувавши розбиття заданої множини то­ чок на дві підмножини, використавши для цього побудову пря­ мої, що проходить через крайні горизонтальні точки, можна значно скоротити кількість переглядів усіх заданих точок при побудові опуклої оболонки. Це дає змогу говорити про часткове застосування методу «розділяй і володарюй».

Варто звернути увагу ще на таке питання: а якщо серед заданих то­ чок виявиться кілька таких, що мають найменше значення по осі абсцис? Яку з них визначати як по­ чаткову? Мабуть, це не має вирі­ шального значення, оскільки на­ віть при розбитті множини точок на дві підмножини ми у гіршому

випадку матимемо одну під множину точок порожню, а до дру­ гої будуть віднесені решта точок (мал. 155). Але й у цьому разі всі точки переглядатимуться лише по одному разу.

Таким чином, можна сформулювати основні етапи алгорит­ му побудови опуклої оболонки методом додавання точок.

1.Упорядкувати всі задані точки за зростанням значень їх абсцис х., зберігши у масиві mast їх початкову нумерацію.

2.Розбити всі точки з номерами від mas2 до masn_1 на дві підмножини, визначивши цей факт перевіркою умови: якщо

(Хі ~ Хта8)(Утаа„ ~ У mas) " U/l ~ Утае)(Хтав„ " Xmas) < 0, ДЄ і = maS2,

270

mas3, ..., masn_x, то такі точки належать до однієї підмножини, у протилежному випадку - до іншої. Відповідні підмножини можуть утворювати два масиви з номерами вершин у порядку зростання їх абсцис. Одночасно необхідно дізнатися, яка з підмножин точок знаходиться над прямою, а яка - під нею. Для цього треба визначити, у яку підмножину потрапить точка з максимальним значенням ординати. Саме з цієї підмножини точок починається побудова опуклої оболонки.

3.Занести у стек порядковий номер першої точки верхньої упорядкованої під послідовності, що відповідає верхній під мно­ жині точок.

4.Якщо не досягнуто останньої точки верхньої підмножини точок, то визначити напрям повороту для наступних двох то­ чок цієї під послідовності. У протилежному випадку перейти до п. 7.

5.Якщо поворот правий, то занести номер нової точки опук­ лої оболонки до стеку і перейти до п. 4.

6.У протилежному випадку зменшити значення вершини стеку на 1 і перейти до п. 4.

7.Завершити побудову верхньої частини опуклої оболонки і перейти до побудови нижньої, розглянувши п. 3-7 для другої під послідовності, врахувавши, що підпослідовність нижніх то­ чок розглядається з кінця до початку.

Наведемо фрагмент основної частини програми, що реалізує описаний алгоритм.

Р 1 [ 1 ] : = р [ 1 ] ; р 2 [ 1 ] : = р [ 1 ] ; х1[1]:=х[1];х2[1]:=х[1];

у1[1]:=у[1];у2[1]:=у[1]; for і := 2 to п - 1 do

begin

if (х[і] - х[1]) * (у[п] - у[1]) - (у[і] - у[1]) * (х[Щ - х[1]) <= 0 then begin inc(w); p1[w] := p[i]; x1[w] :=x[i]; y1[w] :=y[i] end else begin inc(v); p2[v] := p[i]; x2[v] := x[i]; y2[v] := y[i] end;

р1 [w] := p[n]; х1 [w] := x[n]; у1 [w] := у[п]; p2[v] := p[n]; x2[v] := x[n]; y2[v] := у[п];

271