Опукла оболонка, Детальна інформація

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

1. Якщо трійка p1p2p3 утворює правий поворот, то видалити вершину p2 та перевірити трійку p0p1p3.

2. Якщо трійка p1p2p3 утворює лівий поворот, то продовжувати перегляд, перейшовши до трійки p2p3p4.

Оболонка Грехема

1. Знайти внутрішню точку q.

2. Використовуючи q як початок координат, впорядкувати лексикографічно точки множини S у відповідності з полярним кутом та відстанню від q. Організувати точки множини у вигляді кільцевого списку із вказівниками NEXT, PREV та вказівником ПОЧАТОК на першу вершину. Значення TRUE логічної змінної f вказує на те, що вершина ПОЧАТОК досягнута при прямому русі по оболонці, а не в результаті повертання.

3. Обхід

begin

v \xF0AC\xF020ПОЧАТОК; w \xF0AC\xF020NEXT[v]; f \xF0AC\xF020FALSE;

while (NEXT[v] \xF0B9\xF020ПОЧАТОК or f = FALSE) do

begin

if NEXT[v] = w then f \xF0ACTRUE;

if (три точки v, NEXT[v], NEXT[NEXT[v]] утворюють лівий поворот) then v \xF0AC\xF020NEXT[v];

else

begin

ВИДАЛИТИ NEXT[v];

v \xF0AC\xF020PREV[v];

end;

end;

end.

Теорема. Опукла оболонка N точок на площині може бути знайдена за час O(N * logN) при витратах пам’яті O(N).

Метод обхода Джарвіса

Теорема. Відрізок l є ребром опуклої оболонки тоді і тільки тоді, коли всі інші точки заданої множини лежать на l або з одної сторони від нього.

прямих. Для кожної цієї прямої можна визначити за лінійний час розташування інших N-2 точок відносно цієї прямої, тим самим перевіривши чи задовільняє пряма умові теореми. За час O(N3) можна знайти всі пари точок, що визначають ребра опуклої оболонки та розташувати ці точки у вигляді списку послідовних вершин оболонки.

Джарвіс покращив цей алгоритм помітивши, що якщо відрізок pq є ребром оболонки, то повинно існувати інше ребро оболонки з кінцем в точці q. Нехай знайдено точку p1, яка належить опуклій оболонці (яка, наприклад, має максимальну х координату; а якщо таких точок декілька – то серед них взяти точку з мінімальною у координатою). Наступна точка p2 опуклої оболонки – це точка, яка має найменший додатний полярний кут відносно точки p1 як початку координат. І так далі шукаються наступні точки шляхом проходу вкругову опуклої оболонки, породжуючи у потрібному порядку послідовність крайніх точок, по одній на кожному кроці.

Обхід Джарвіса

p[1] \xF0AC\xF020точка з найменшою y координатою;

p[2] \xF0AC\xF020точка з множини S, для якої кут між прямою p[2] - p[1] та віссю Ox найменший;

print (p[1], p[2]);

i \xF0AC\xF0202;