Материал: 252_337

Алгоритм Джарвіса

Як видно з попередніх двох методів, побудова опуклої обо­ лонки починається з визначення стартової точки, що належить цій опуклій оболонці. Такими точками завжди є крайні точки: ліва, верхня, права і нижня. Залежно від обраного методу, стартовою визначається одна з них. Наступною точкою опуклої оболонки серед решти точок обов'язково буде точка з наймен­ шим кутом відхилення від стартової. Це обумовлено тим, що при повороті, наприклад, наліво від стартової точки першою точкою, яка трапиться на цьому шляху, буде точка з наймен­ шим кутом повороту відносно стартової (мал. 162).

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

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

Розглянемо покрокове виконання алгоритму Джарвіса (мал. 162). На малюнку зображено задані точки у довільному порядку. Стартовою точкою є точка рь - найлівіша нижня точ­ ка серед усіх заданих, тобто така, у якої найменше значення по

282

осі абсцис та по осі ординат. Занесемо її порядковий номер у шукану послідовність номерів точок, що утворюють опуклу оболонку. Виконаємо паралельне перенесення початку коор­ динат у цю точку і серед решти точок визначимо ту, що має найменший лівий кут відносно стартової (мал. 162, а). Такою точкою у нашому прикладі буде точкаpQ . Перше ребро опуклої оболонки знайдено, воно сполучає точки р5 і р9. Допишемо по­ рядковий номер точки рд у шукану послідовність і перейдемо до наступного кроку.

На другому кроці виконання алгоритму паралельно перене­ семо початок координат у точку р9 (мал. 162, б) і визначимо точку, яка має найменший лівий кут відхилення від точки р9 у побудованій системі координат. Такою є точкаps .

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

На малюнку 163, є за послідовністю отриманих порядкових номерів заданих точок побудована шукана опукла оболонка.

Опишемо алгоритм Джарвіса для побудови опуклої оболонки.

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

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

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

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

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

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

283

284

побудованої опуклої оболонки в порядку їх обходу проти го­ динникової стрілки.

Перш ніж навести фрагмент програми, що реалізує описа­ ний алгоритм, розглянемо його математичну складову.

На кожному кроці виконання алгоритму при паралельному перенесенні початку координат у поточну стартову точку не­ обхідно робити перерахунок координат тих точок, що надалі розглядаються. Перераховані координати стартової точки при перенесенні у неї початку координат набудуть значення (0; 0). Якщо позначити реальні координати поточної стартової точки (xst; yst), а досліджуваної точки (xt; yt), то перетворені координа­ ти і-ї точки будуть обчислюватися за формулами дг/ = xt - xst,

від'ємними (мал. 164).

Так само, як і для алгоритму Грехема, обчислення значення ку­ та можна звести до обчислення значення його синуса за формулою

у—у,

' =. У правій координатній півплощині протн­

у в ~ * J 2 +0/І -&*)2

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

285

Отже, фрагмент основної частини програми, що реалізує алго­ ритм Джарвіса для побудови опуклої оболонки, може бути таким:

|x_min := x[i]; y_min := y[i]; p s t := і end;

{Визначення найправішої верхньої точки.} if (х[і] > xjmax) or ((x[i] = x_max) and (y[i] < y m a x ) )

then begin

| x_max := x[i]; y_max := y[i]; p e n d := і end;

Процедура include визначає вершини опуклої оболонки і за­ лежить від напряму пошуку: для нижньої частини ланцюга во­ на працює з параметром рг = 0, а для верхньої - рг = 1:

procedure include(pr: byte);

var angl, angljnin, d_k_st, d_k_i: real; begin

{Визначення частини ланцюга вершин опуклої оболонки, що будується.}

if рг= 0 then anglmin := 2 else angljnin := -2;

then begin

{Обчислення відстані від точки pjst, яка на даний момент є кандидатом} {для включення до послідовності вершин опуклої оболонки,}

{до точки р[к], з якої ведеться спостереження.}

d_k_st := sqrt(sqr(x[p_st] - x[p[k]]) + sqr(y[p_st] - y[p[k]]));

286