Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TA_last_u3.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆

Метод обходу Грехема

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

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

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

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

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

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 як початку координат. І так далі шукаються наступні точки шляхом проходу вкругову опуклої оболонки, породжуючи у потрібному порядку послідовність крайніх точок, по одній на кожному кроці.

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

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

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

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

i 2;

while (p[i] p[1]) do

begin

p[i + 1] точка з множини S, для якої кут p[i - 1] p[i] p[i + 1] є найбільшим;

i i + 1;

print (p[i]);

end.

Теорема. Часова оцінка обходу Джарвіса дорівнює O(N2).

Оскільки всі N точок можуть лежати на опуклій оболонці, а алгоритм Джарвіса вимагає лінійний час для знаходження кожної наступної точки оболонки, то в найгіршому випадку часова оцінка дорівнює O(N2). Обхід Джарвіса є ефективним, якщо кількість вершин опуклої оболонки h є малою у порівнянні зі значенням N – часова оцінка у цьому випадку дорівнюватиме O(N * h).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]