Материал: 252_337
begin |
|
|
{що виявилися у нижній підмножині.} |
||||
с := р2[і]; р2[і] := p2[v - і + 1]; |
p2[v - і + 1] := с; |
|
|||||
с1 :=х2[і];х2[і] : = x 2 [ v - i + 1 ] ; x 2 [ v - i + 1] : = с 1 ; |
|
||||||
с1 :=у2[і];у2[і] : = y 2 [ v - і + 1]; y 2 [ v - і + 1] : = с 1 ; |
|
||||||
end |
|
|
|
|
|
|
|
else for і := 1 to w div 2 do |
|
|
|
|
|
||
begin |
|
|
|
|
|
|
|
c : = p 1 [ i ] ; p 1 [ i ] : = p 1 [ w - i + 1];p1[w і + 1 ] := c; |
|
||||||
d |
:=x1[i];x1[i] : = x 1 [ w - i + 1];x1[wi + 1] |
= |
c 1 ; |
|
|||
d |
: = y 1 [ i ] ; y 1 [ i ] : = y 1 [ w - i + 1];y1[w |
+ 1] |
= |
c 1 ; |
|
||
end; |
|
|
|
|
|
|
|
for і := 1 to w - 1 do |
|
{Злиття точок із двох підмножин в одну.} |
|||||
begin р[і] := р1 [і]; х[і] := х1 [і]; у[і] := у1 [і] end; |
|
|
|||||
fori := 1 t o v - 1 do |
|
|
|
|
|
|
|
begin p[i + w - 1] := p2[i]; x[i + w - 1] := x2[i]; y[i + w - |
1] := y2[i]; end; |
||||||
count := 1; stack[count] := p[1]; |
|
|
|
|
{Блок ініціалізації} |
||
St := []; |
|
{для подальшої побудови опуклої оболонки.} |
|||||
for і |
:= 1 to n do st := st |
+ [р[і]]; |
|
|
|
|
|
і := 2; k := і; І := і + 1; flag := false; |
|
|
|
|
|
||
repeat |
|
|
|
|
|
|
|
х_0 := x[stack[count]]; у_0 := y[stack[count]]; |
|
|
|
||||
х_1 :=x[k];y_1 :=y[k]; |
|
|
|
|
|
|
|
x _ 2:=x[l];y _ 2:=y[l]; |
|
|
|
|
|
|
|
|
|
|
{Якщо виконується правий поворот,} |
||||
if (х_1 х_0) * (у_2 - у_0) - (х_2 - х_0) * (у_1 - у_0) <= 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 |
|
|
|
|
|
|
|
l : = k + 1 ; |
|
|
|
|
|
|
|
while not(p[l] in st) and (I <= n) do inc(l); |
|
|
||||
|
if I > n then flag := true |
|
{Якщо досягнута остання точка,} |
||||
|
end; |
|
|
|
|
{то побудова завершується.} |
|
until flag;
х_0 := x[stack[count]]; у_0 := y[stack[count]]; {Перевірка можливого включення} х_1 :=х[к];у_1 :=у[к]; {до опуклої оболонки останньої точки.} х _ 2:=х[1];у _ 2:=у[1];
if (х_1 - х_0) * (у_2 - у_0) - (х_2 - х_0) * (у_1 - у_0) <= 0 then begin inc(count); stack[count] := k end;
Процедура сортування точок:
procedure sort(L, R: word); var i, j, L_R: word; w: real; begin
i:=L;j:=R;L _ R:=(L + R)div2; w:=x[L_R];
272
repeat
while (x[i] < w) or ((x[i] = w) and ((y[i] < y[L_R]))){l~loujyK зліва нижньої точки.} do і :=i + 1;
while (w < x[j]) or ((x[j] = w) and ((y[j] > y[L_R]))) {Пошук справа верхньої точки.}
d o j : = j - 1 ; |
|
if і <= j then |
|
begin |
|
d :=x[i]; x[i] := x[j]; x[j] := d; |
{Обмін координат точок.} |
c1 :=y[i];y[i]:=y[j];y[j] : = c 1 ; |
|
c := p[i]; p[i] := p[j]; p[j] := c; |
{Обмін номерів точок.} |
i:=i + 1 ; j : = j - 1 ; |
|
end; |
|
until і >j; |
|
if j>Lthensort(L,j); |
|
if і < R then sort(i, R) |
|
end; |
|
Визначимо оцінку описаного алгоритму побудови опуклої оболонки методом додавання точок. Перегляд точок та їх аналіз щодо входження до опуклої оболонки оцінюється як О(п). Для поділу заданої множини точок на дві підмножини необхідно пе реглянути кожну точку лише по одному разу, тобто оцінка ефективності цієї частини алгоритму становить 0(п). Залиши лося врахувати упорядкування множини заданих точок за зрос танням відповідно до значень по осі абсцис 0(п logn). Таким чи ном отримаємо таку складність алгоритму: 0(п logn + п + п) = = 0(п (logn + 2)) = 0(п logn). Цей результат виглядає значно кра ще, ніж наведений вище повноперебірний варіант.
Для тестування даного алгоритму можна запропонувати розглянути такі множини точок, коли всі вони однозначно роз биваються на дві підмножини і жодна з точок не лежить на прямій поділу; коли в одну з під множин не потрапляє жодної точки, а це може бути тоді, якщо точки цієї підмножини ле жать на одній горизонталі; коли всі точки заданої множини утворюють прямокутник; коли лише деякі точки заданої мно жини утворюють прямокутник, а решта точок розміщені у се редині. Усі ці варіанти множин заданих точок варто перевіри ти для різної їх кількості, наприклад від 10 до 1000.
Алгоритм Грехема
Наступні два алгоритми побудови опуклої оболонки відрізняються від попереднього лише тим, що пропонують свої ідеї щодо порядку розгляду точок заданої множини. Адже саме ця частина алгоритму дає змогу скоротити кількість пере глядів заданих п точок для подальшого аналізу щодо їх вклю чення до опуклої оболонки.
Алгоритм Грехема ґрунтується на аналізі величин кутів (мал. 156). Для побудови цих кутів спочатку необхідно ви-
273
значити початкову точку, що є найлівішою серед решти за даних точок, тобто має най менше значення по осі абсцис. Якщо таких точок кілька, то серед них вибирається най нижча, тобто така, у якої зна чення по осі ординат наймен ше. На малюнку 156 такою точкою є точка pv
Оскільки інформація про кожну точку задається коор динатами на площині, то можна вважати, що існує дея ка декартова система коорди
нат, і тому через точку р1 можна провести пряму, паралельну осі ординат. З'єднаємо відрізками точку р1 з рештою точок р2, р3, ...,рпі розглянемо кути, які утворили ці відрізки із прямою, проведеною через точкурх . Ці кути матимуть значення від -л/2 до я/2, оскільки за побудовою всі точки заданої множини зна ходяться правіше прямої, що проходить через точкур1 т або зна ходяться на цій прямій.
Далі логіка алгоритму Грехема є досить прозорою. Не обхідно упорядкувати точки р2, р3, ..., рп відповідно до збіль шення кута між відрізками, що з'єднують ці точки з точкоюрх , та прямою, що проходить черезр1 . Оскільки точкарх обов'язко во за побудовою входить до опуклої оболонки, то для включен ня до неї решти точок необхідно здійснювати їх перегляд саме за такою упорядкованою послідовністю. Це дасть змогу пере глядати кожну точку лише один раз.
Включення точок до опуклої обо лонки здійснюється з використан ням стеку, як було описано у методі додавання точок. У нашому випад ку опукла оболонка будується проти годинникової стрілки, і тому для визначення її вершин треба викону вати лише ліві повороти. Цей мо мент продемонстрований на малюн ку 157: при переході від точки р2 до
Мал. 157 точки р3 було виконано лівий пово рот, а від точкир3 до точкир4 - правий, тому точкар3 не входить до опуклої оболонки і її необхідно виключити із стеку.
Виконаємо алгоритм Грехема покроково на прикладі, на веденому на малюнку 156. Покрокові результати виконання зображені на малюнках 158-160: у верхній частині - графічне зображення, у нижній - поточний стан стеку.
274
а) a
|
I |
2 |
6) |
1 |
I 2" |
|
|
275
a) |
1 1 2 I 3 | 4 |6І |
б) I 1 I 2| 3 | 4 | 6 | 7 |
|||
|
|
|
|
|
|
3) |
| 1 |
| 2 1 3 | 4 ] 6 | |
7 |
г) |
I 1 1 2 1 3 | 4 |
| 6 7 |
12 3 4 6 7
276