WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Опукла оболонка - Реферат

Опукла оболонка - Реферат

абсциси.
Означення. Точка p опуклої множини S називається крайньою, якщо не існує пари точок a, b S таких, що лежить на відкритому відрізку ab.
Множина E крайніх точок S представляє собою найменшу підмножину S, яка має властивість: conv(E) = conv(S), при чому Е в точності співпадає з множиною вершин conv(S).
Для знаходження опуклої оболонки скінченної множини необхідно виконати наступне:
1. Визначити крайні точки;
2. Впорядкувати ці точки так, щоб вони утворювали опуклий многокутник.
Теорема. Точка p не є крайньою плоскої опуклої множини S тоді і тільки тоді, коли вона лежить в деякому трикутнику, вершинами якого є точки з S, але сама вона не є вершиною цього трикутника.
Існує O(N3) трикутників, яківизначаються N точками множини S. Отже за час O(N3) можна визначити, чи є задана точка крайньою. Повторення цієї процедури для всіх N точок множини S вимагає часу O(N4).
Точка P не є крайньою, оскільки вона лежить всередині трикутника P1P2P3.
Теорема. Промінь, який виходить із внутрішньої точки обмеженої замкненої фігури F, перетинає границю F рівно в одній точці.
Теорема. Послідовні вершини опуклого многокутника розташовані в порядку, якому відповідає зміна кута відносно довільної внутрішньої точки.
Теорема. В якості внутрішньої точки q можна взяти центроїд довільних трьох неколінеарних точок.
Для цього беруться дві довільні точки та шукається така третя точка з інших N - 2 точок, яка не лежить на прямій, що визначається першими двома.
Задача. На площині дано дві точки p1 та p2. Яка з цих точок має більший полярний кут?
p2 утворює з віссю Ох строго менший полярний кут, ніж p1 тоді і тільки тоді, коли трикутник (O, p2, p1) має строго додатню площу (або точка P1 лежить зліва від прямої OP2).
Приклад. Площа трикутника OP2P1 дорівнює Ѕ * P2 P1 = Ѕ * = Ѕ * (30 - 6) = 12.
Метод обхода Грехема
Знайдемо внутрішню точку 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).
Алгоритм апроксимації опуклої оболонки
При знаходженні наближеної опуклої оболонки ми розмінюємо точність на простоту та ефективність алгоритму.
Знайдемо мінімальне та максимальне значення х координати точок множини S та розіб'ємо вертикальну полосу між ними на k полос рівної ширини. В кожній із цих k полос шукаються дві точки, які мають мінімальну та максимальну у координату (обирається 2k точок). Обираються також точки з екстремальними значеннями х координати; якщо їх декілька, то обираються дві точки з екстремальними значеннями у координати (максимум обирається 4 точки). Обрана множина містить не
Loading...

 
 

Цікаве