Опукла оболонка

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

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

3. Обхід

begin

v ПОЧАТОК; w NEXT[v]; f FALSE;

while (NEXT[v] ПОЧАТОК or f = FALSE) do

begin

if NEXT[v] = w then f TRUE;

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

else

begin

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

v PREV[v];

end;

end;

end.

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

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

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

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

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