Припустимо, що внутрішня точка вже знайдена і вона є початком координат. Упорядкуємо лексографічно N точок відповідно до значень полярного кута і відстані від початку координат.
При виконанні сортування не потрібно обчислювати дійсну відстань між двома точками, так як треба лише порівняти дві величини. Порівняння відстаней необхідно виконувати лише у випадку, якщо дві точки мають один і той же полярний кут. Але тоді вони лежать на одній прямій з початком координат, і порівняння в цьому випадку тривіальне (мал. 4.5). Якщо точка не є вершиною опуклої оболонки, то вона є внутрішньою точкою для деякого трикутника (Орq), де р і q - послідовні вершини опуклої оболонки.
Суть алгоритму Грехема полягає в однократному перегляді впорядкованої послідовності точок, в процесі якого вилучаються внутрішні точки. Точки, що лишилися, є вершинами оболонки, які подано у відповідному порядку.
Мал. 4.5. Початок обходу точок у методі Грехема. Вершина р2 вилучається, якщо кут р1р2р3 виявляється вогнутим.
Перегляд починається з точки, яку позначено як ПОЧАТОК. У якості цієї точки можна взяти найправішу з найменшою ординатою точку з даної множини, яка напевне є вершиною опуклої оболонки.
Трійки послідовних точок багатократно перевіряються у порядку обходу проти годинникової стрілки з метою визначення, чи утворюють вони кут, більший або рівний p.
Якщо внутрішній кут р1р2р3p, р1р2р3 утворюють "правий поворот"(D > 0),
інакше р1р2р3 утворюють "лівий поворот"(D < 0). D визначається за наступною формулою ( 4.1):
Залежно від результатів перевірки кута, який утворюється трійкою вершин, можливі два варіанти продовження перегляду:
р1р2р3 утворюють "правий поворот". Вилучити вершину р2 і перевірити трійку р0р1р3.
р1р2р3 утворюють "лівий поворот". Продовжити перегляд, перейшовши до трійки р2р3р4.
Перегляд завершується тоді, коли, обійшовши всі вершини, знову приходимо у вершину ПОЧАТОК.
Алгоритм обходу Грехема
procedure ОБОЛОНКА_ГРЕХЕМА(S)
Знайти внутрішню точку q.
Використовуючи q як початок координат, упорядкувати точки множини S лексографічно відповідно до полярного кута і відстані від q. Організувати точки множини у вигляді кільцевого двічі зв'язаного списку з посиланнями НАСТУП і ПОПЕР і вказівником ПОЧАТОК на першу вершину. Значення true логічної змінної f вказує на те, що вершина ПОЧАТОК виявилася досягнутою при прямому просуванні по оболонці, а не в результаті повернення.
(Обхід)
begin v := ПОЧАТОК; w := ПОПЕР[v]; f := false ;
while (НАСТУП[v] ПОЧАТОК or f = false) do
begin if (НАСТУП[v]=w) then f := false;
if (три точки v, НАСТУП[v], НАСТУП[НАСТУП[v]] утворюють "лівий поворот") then v := НАСТУП[v]
else begin ВИЛУЧИТЬ НАСТУП[v];
v := ПОПЕР[v];
end;
end;
end.
Після завершення алгоритму список містить впорядковані вершини оболонки. Теорема 4.6. Опукла оболонка N точок на площині може бути знайдена методом Грехема за час O(N log N) при використанні пам'яті O(N) з використанням лише арифметичних операцій і порівнянь. Доведення. Із попереднього обговорення АГ зрозуміло, що в ньому використовуються лише арифметичні операції та порівняння. Кроки 1 і 3 потребують лінійного часу, тоді як крок 2, який є визначальним за часом роботи, виконується за час O(N log N). Для представлення зв'язного списку
точок достатньо O(N) пам'яті. Приклад 3.Для заданої множини точок р1, р2, р3, р4, р5, р6, р7 застосувати обхід Грехема.
Мал. 4.6.
Опукла оболонка N точок на площині може бути знайдена методом Грехема за час O(N logN) при використанні пам'яті O(N) з використанням лише арифметичних операцій і порівнянь.
p, р1р2р3 утворюють "правий поворот"(D > 0),
інакше р1р2р3 утворюють "лівий поворот"(D < 0).
ПОЧАТОК or f = false) do
