Материал: 252_337
1 |
2 |
3 |
4 |
5 |
12 |
3 |
4 |
5 |
6 |
12 |
3 |
4 |
5 |
6 |
7 |
|
12 |
3 |
4 |
5 |
6 |
7 |
|
||
в) |
1 1 | 2 | 3 |
[ 4 |
| 6 |Ю|11| |
|
г) | |
1 | 2| 3 | 4 J 6 |10|11| |
|
||||||||
|
|
|
|
|
|
|
|
Мал. 160 |
|
|
|
|
|
|
|
На першому кроці визначено стартову точку рх |
і упорядковано |
||||||||||||||
решту точок за зростанням кута відносно точки рх |
(мал. 158, а). |
||||||||||||||
Порядковий номер точки рх |
занесено до стеку. |
|
|
|
|
|
|||||||||
На другому кроці розглядаються точки р2 |
ір3 |
та напрям кута |
|||||||||||||
повороту між ними. При цьому спостереження ведеться з точки, що знаходиться у вершині стеку, тобто з точки/jj (мал. 158, б). Напрям повороту лівий, тому точка р2 заноситься до стеку.
На третьому кроці виконання алгоритму спостереження за напрямом повороту від точки ps до точки рі ведеться із точки р2, оскільки на поточний момент саме ця точка знаходиться у вершині стеку (мал. 158, в). Поворот, показаний на малюнку, є лівим, і тому точкар3 також заноситься до стеку.
Аналогічна ситуація спостерігається і на четвертому кроці, коли із точки р3 аналізується поворот від точки р4 до точки рь. Точкар4 заноситься до стеку і стає її вершиною (мал. 158, г).
277
Виконання п'ятого кроку зображене на малюнку 158, д. Дивлячись із точки р4 у точку рь, а потім переходячи до точки р6, ми виконаємо правий поворот, що суперечить виконанню алгоритму. Це означає, що точка р5 не може бути вершиною опуклої оболонки і тому вона вилучається із подальшого пере гляду. Надалі точкарь зображується незафарбованою. Точкар4 вилучається зі стеку зменшенням порядкового номера його вершини на 1, і тим самим відбувається повернення у точку р3.
Шостий крок виконується традиційно: із точки р3, що на да ний момент знаходиться у вершині стеку, дивимось у точку р4, а із неї - у точку р6 (мал. 158, є). При цьому виконується лівий поворот, тому точкар4 знову заноситься до стеку, однак при цьо му точка р5 уже виключена з перегляду.
Розглянемо малюнки 159, а і 159, б, що відповідають сьомо му і восьмому крокам. На цих кроках виконується лівий пово рот, тому точки р6 ір7 заносяться до стеку.
На дев'ятому та десятому кроках (мал. 159, в, г) відбуваєть ся вже відома ситуація, коли спостереження ведеться із точок р7 т а р 8 і при цьому виконується правий поворот. Тому надалі спочатку точка р8, а потім і точка р7 виключаються із перегля ду і відбувається повернення у стеку знову до точки р4.
Одинадцятий та дванадцятий кроки (мал. 159, д, є) спочат ку дають змогу знову повернути у стек точку р6, оскільки виконується лівий поворот від точки р6 до точки р9, а потім ви ключити точкур6 зі стеку, а точкур9 - з подальшого перегляду.
Тринадцятий крок виконання алгоритму Грехема знову повер тає до точкир4, яка знаходиться на даний момент у вершині стеку j (мал. 159, 160, а). При дослідженні повороту із точки р6 до точки р10 фіксується лівий поворот. Це саме відбувається і на чотирнад цятому кроці (мал. 160, б), томур6 ір10 дописуються у стек.
На останньому, п'ятнадцятому, кроці (мал. 160, в), на яко му у поле зору потрапляє стартова точка pv виконується лівий поворот від точки ри, тому точка з порядковим номером 11 останньою записується до стеку.
Таким чином, після завершення виконання алгоритму Грехе ма у стеку знаходиться послідовність номерів вершин, у резуль таті обходу яких буде побудовано опуклу оболонку (мал. 160, г).
Після такого детального розгляду покрокового виконання алгоритму Грехема на конкретному прикладі можна навести його опис у словесній формі.
1.Визначити початкову точку як таку, що має найменше значення по осі ординат. Якщо таких точок кілька, то серед них визначити точку з найменшим значенням по осі абсцис.
2.Упорядкувати решту точок (і - 2, 3, ..., п) за зростанням кута між відрізками, що з'єднують ці точки з початковою точ-
278
jcoio, визначеною у п. 1, та прямою, проведеною через початко ву точку, паралельно осі абсцис.
3.Занести до стеку визначену початкову точку р1.
4.Визначити для упорядкованої послідовності точок і = 2.
5.Якщо не досягнуто останньої точки упорядкованої послідовності, то для двох точок з порядковими номерами і та
і+ 1 визначити напрям повороту. У протилежному випадку перейти до п. 8.
6.Якщо поворот лівий, то занести нову точку з порядковим номером і до стеку, перейти до наступної не виключеної з пере гляду точки упорядкованої послідовності. Перейти до п. 5.
7.У протилежному випадку виключити з подальшого пере гляду точку і та зменшити значення вершини стеку на 1. Пе рейти до п. 4.
8.Розглянути останню трійку точок р„_і> Рп> Рі і Я К Щ° Д л я них виконується правило лівого повороту, то включити точку
рп до опуклої оболонки.
9. Завершити побудову опуклої оболонки, інформація про яку знаходиться у стеку.
Розглянемо питання практичної реалізації описаного алго ритму, а саме: яким чином визначати кути для подальшого
упорядкування заданих точок. |
|
|
|
|
||||
Нехай задано три точки pv |
р2, р3 |
У |
|
|
|
|||
|
|
|
||||||
(мал. 161). Точкою р1 |
повинна бути |
|
|
|
||||
найлівіша і найнижча точка серед |
Уз |
Щ''" |
|
щ |
||||
|
|
|||||||
усіх інших. Провівши через точку |
|
|
||||||
|
1 / |
|
|
|||||
р1 пряму, паралельну осі ординат, |
|
|
|
|||||
визначимо |
два прямокутних |
три |
Уі |
«^>! |
|
|
||
кутники з вершинами у точках pv |
|
[ N. |
|
|
||||
р2, р2' та |
рх, р3, ps'. |
Відношення |
|
|
|
|
||
прилеглих |
катетів |
до гіпотенуз |
|
|
|
|
||
відповідних прямокутників |
три |
|
щ1 |
|
|
|||
кутників |
визначає |
синуси |
кутів |
У* |
- - |
- - > р 2 |
||
^-Р?РіР2 і ^-РзРіРз- Зрозуміло, що у |
|
|
|
|
||||
0 |
* 1 |
X 3 *а X |
||||||
разі, коли значення відповідних |
||||||||
|
|
|
||||||
кутів різне, то це означатиме, що |
|
|
|
|
||||
|
|
|
|
|||||
таке саме відношення збережеться і для значень синусів цих кутів.
Цю властивість можна використати для упорядкування зада них точок множини за зростанням кута. Синус кута між точка
ми з координатами |
(х^, г/х) та (xt; yt) визначається за формулою |
||
~Т |
у.' —у, |
,. |
Оскільки всі точки заданої множини за |
побудовою лежать у правій півплощині відносно осі ординат, то значення синусів шуканих кутів буде змінюватися від -1 до 1. Тобто, упорядковуючи точки за значенням наведеного виразу,
279
отримаємо зростаючу послідовність, а відповідно обхід упоряд кованих за цією ознакою точок множини виконуватиметься проти годинникової стрілки.
Перейдемо до тексту програми. Можна запропонувати та кий фрагмент її основної частини:
x m i n := maxint; y_min := maxint; |
|
{Блок ініціалізації.} |
||||
for і := 1 to n do |
|
|
|
|
||
begin |
|
|
|
|
|
|
read(f_in, х[І], у[І]); |
|
{Введення початкових даних та} |
||||
if (х[і] < x_min) or ((x[i] = xmin) and (y[i] < yjnin)) {одночасний пошук} |
||||||
then begin |
|
|
|
|
|
|
|
|x_min := x[i]; yjni n := y[i]; p st := і |
{стартової точки.} |
||||
|
end; |
|
|
|
|
|
end; |
|
|
|
|
|
|
for і |
:= 1 to n do |
|
|
|
|
|
if І <> p_St |
{Обчислення синусів лівих кутів відхилення від стартової} |
|||||
then |
|
|
|
{для кожної точки.} |
||
angl[i] := (у[і] - y[p_st])/sqrt(sqr(x[i] - x[p_st]) + sqr(y[i] - y[p_st])) |
||||||
else angl[i] := 0; |
{Для стартової точки кут відхилення дорівнює 0.} |
|||||
for І := 1 to П do |
{Ініціалізація послідовності номерів точок,} |
|||||
р[і] |
:= І; |
{упорядкованих за зростанням лівого кута відхилення.} |
||||
SOrt( 1, п); |
{Упорядкування точок за зростанням лівого кута відхилення.} |
|||||
|
|
{Ініціалізація стеку і множини точок, що можуть бути} |
||||
count := 1; stack[count] := 1; st := [1 ..п]; |
{вершинами опуклої оболонки.} |
|||||
|
|
|
{Визначення номерів першої пари} |
|||
і := 2; k := і; І := і + 1; flag := false; |
|
{досліджуваних точок.} |
||||
repeat |
|
|
|
{Побудова опуклої оболонки.} |
||
Х_І := х[р[к]]; у_І := у[р[к]]; |
{Обчислення координат досліджуваних точок.} |
|||||
x_st := x[p[stack[count]]]; y_st := y[p[stack[count]]]; |
|
|||||
xJ1 |
:=x[p[l]];y_i1:=y[p[l]]; |
|
|
|
|
|
|
|
|
|
|
{Визначення напряму} |
|
if (x_i - x_st) * |
(y_i1 - y_st) - |
(х_І1 - x_st) * |
( y j - y_st) >= 0 |
{повороту.} |
||
|
|
|
{Якщо поворот лівий, то занесення} |
|||
then begin inc(count); stack[count] := k end |
{у стек нової точки,} |
|||||
|
|
{у протилежному випадку - повернення до попередньої точки} |
||||
|
|
|
|
{і виключення точки з номером /} |
||
else begin dec(count); st := st - [p[l]] end; |
{із подальшого розгляду.} |
|||||
k := Stack[count] + 1; |
{Пошук наступної пари досліджуваних точок.} |
|||||
while not(p[k] in st) and (k < n) do inc(k); |
|
|
|
|||
|
|
|
{Встановлення ознаки щодо досягнення} |
|||
if k = n then flag := true; |
|
|
{останньої заданої точки.} |
|||
if not flag |
|
{Якщо остання точка ще не досягнута, то} |
||||
then |
|
|
|
|
|
|
begin |
|
|
|
|
|
|
|
І := k + 1; |
|
{визначення другої точки досліджуваної пари.} |
|||
|
while not(p[l] in st) and (I <= n) do inc(l); |
|
|
|||
if I > n then flag := true end;
until flag;
4
280
xj := x [ p [ k ] ] ; yj := y [ p [ k ] ] ; |
{Дослідження останньої трійки точок pn _,, рп, р,.} |
|
x_st := x[p[stack[count]]]; y_st := y[p[stack[count]]]; |
|
|
xJ1:=x[p[1]];y_i1:=y[p[1]]; |
|
|
|
{Якщо виконується лівий поворот, то} |
|
if ( x j - x_st) * (y_i1 - y_st) - (x_i1 - x_st) * (y_i - y_st) >= 0 |
|
|
|
{остання точка заноситься} |
|
t h en begin inc(count); stack[count] := k end; |
{до стеку.} |
|
Сортування заданих точок за лівими кутами їх відхилення від стартової точки може бути представлене такою процедурою:
procedure sort(L, R: word);
var і, j, c1, L R: word; c, w: real; begin
i:=L;j:=R;L_R:=(L + R)div2; w :=angl[L_R];
|
{Пошук у лівій частині послідовності крайньої зліва точки,} |
repeat |
{що має менший кут відхилення.} |
while (angl[i] < w) or ((anglfi] = w) and ((y[p[i]] > y[p[L_R]]) or(x[p[i]]<x[p[L_R]])))doi:=i + 1;
{Пошук у правій частині послідовності крайньої зверху точки,}
{що має менший кут відхилення.}
while (w < anglfj]) or ((angl[j]= w) and ((y[p[j]] < y[p[L_R]]) or(x[p[j]]>x[p[L_R]])))doj:=j-1;
if і <=jthen begin
|
{Обмін у зростаючій} |
c := angl[i]; angl[i] := angl[j]; angl[j] := c; |
{послідовності кутів.} |
{Обмін у зростаючій послідовності} |
|
с1 :=р[і]; р[і] :=p[j]; p[j] :=с1; |
{номерів вершин.} |
i:=i + 1 ; j : = j - 1 ; end;
until і > j;
if j>Lthensort(L,j); if і < R then sort(i, R) end;
Оцінка ефективності алгоритму Грехема становить 0(п logn). Це обумовлюється тим, що упорядкування множини заданих точок у найкращому випадку, наприклад за допомогою методу швидкого сортування, виконується за 0(п logn) операцій, а включення точок до опуклої оболонки є лінійною операцією і становить О(п), що впливає на остаточний результат оцінки.
Щодо тестування алгоритму Грехема, то варто перевірити його на тих самих тестах, що і алгоритм побудови опуклої обо лонки методом додавання точок.
281