.

Опукла оболонка (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
306 2502
Скачать документ

Реферат на тему:

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

Означення. Афінна геометрія складається з множини скалярів S (дійсних
чисел), множини точок P та множини вільних векторів V (або просто
векторів). Точки використовуються для задання положення, а вектори – для
задання напрямку та величин, хоча вони і не мають фіксованого положення
у просторі.

Операції афінної геометрії:

1. добуток скаляра на вектор: S * V ??V;

2. додавання векторів: V + V ??V;

3. віднімання точок: P – P ??V;

4. додавання точки та вектора: P + V ??P;

додавання векторів віднімання точок додавання точок та вектора

Різницею двох точок p та q буде вектор, який направлево з q до p.

Кількість операцій можна розширити. Наприклад, різницю векторів можна
визначити як u – v = u + (-1) * v, а ділення вектора на скаляр як v / a
= (1 / a) * v. Але не можна додавати дві точки або множити точку на
скаляр.

Означення. Нехай в Ed задано k різних точок p1, p2, …,pk. Множина
точок p таких що

p = a1p1 + a2p2 + … + akpk (ai ??R, a1 + a2 + …+ ak = 1)

називається афінною множиною, породженою точками p1, p2, …, pk, а p
називається афінною комбінацією точок p1, p2, …, pk.

Афінна комбінація є частковим випадком лінійної комбінації (вводиться
додаткова умова a1 + a2 + …+ ak = 1). При k = 2 афінна множина – це
пряма, що проходить через дві точки p1 та p2.

Приклад. Нехай дано дві точки p1, p2 та число а. Позначимо через Aff(p0,
p1, a) комбінацію (1 – a) * p1 + a * p2 = p1 + a * (p2 – p1). Ліва
частина рівності містить недопустиму операцію (додавання точок), але
еквівалентний їй алгебраїчний вираз правої частини є допустимим. Якщо p1
??p2, то Aff(p0, p1, a) лежить на прямій p1p2. Коли а пробігає всі
дійсні значення, то вираз Aff(p0, p1, a) пробігає всі точки прямої p1p2.
При a ??[0; 1] значення Aff(p0, p1, a) пробігає всі точки відрізку [p;
q].

Для представлення векторів та точок в афінному просторі використовуються
гомогенні координати. При роботі з d вимірним афінним простором
координати будемо представляти (d + 1) – кортежами дійсних чисел. Перший
елемент кортежа дорівнює 1 для точки і 0 для вектора. Інші d елементів
кортежа відповідають безпосередньо координатам.

P(1; 1; 3), Q(1; 4; 1), u(0; 1; 2).

P – Q = (1-1; 1-4; 3-1) = (0; -3; 2).

Означення. Три точки p, q, r на площині мають додатню орієнтацію, якщо
вони утворюють трикутник, орієнтований проти годинникової стрілки та
від’ємну орієнтацію, якщо обхід трикутника pqr відбувається за
годинниковою стрілкою. Три точки p, q, r мають нульову орієнтацію, якщо
вони лежать на одній прямій.

додатня нульова від’ємна

Орієнтація визначається знаком детермінанта, визначеного координатами
трьох точок в гомогенних координатах:

Означення. Нехай в просторі Ed задана підмножина L. Афінною оболонкою
aff(L) множини L називається найменша афінна множина, яка містить L.

Афінною оболонкою відрізка є пряма, афінною оболонкою плоского
многокутника є площина.

Означення. Нехай в Ed задано k різних точок p1, p2, …,pk. Множина
точок p таких що

p = a1p1 + a2p2 + … + akpk (ai ??R, ai ??0, a1 + a2 + …+ ak = 1)

називається опуклою множиною, породженою точками p1, p2, …, pk, а p
називається опуклою комбінацією точок p1, p2, …, pk.

Опукла комбінація є звуженням афінної комбінації. При k = 2 опуклою
множиною є відрізок, який сполучає задані точки.

Означення. Нехай в просторі Ed задана підмножина L. Опуклою оболонкою
conv(L) множини L називається найменша опукла множина, яка містить L.

Означення. Поліедральною множиною в називається перетин скінченної
множини замкнених півпросторів (півпростір – це частина Ed, розташована
по одну сторону від деякої гіперплощини).

Поліедральна множина є опуклою, оскільки півпростір є опуклим та перетин
опуклих множин є опуклою множиною. Плоскі многокутники та тривимірні
многогранники є прикладами скінченних поліедральних множин. Скінченну d
– мірну поліедральну множину будемо називати опуклим d – політопом (або
просто політопом).

Теорема. Опукла оболонка скінченної множини точок в є опуклим політопом.
Кожний опуклий політоп є опуклою оболонкою деякої скінченної множини
точок.

Опуклий політоп задається описом його границі, яка складається з граней.
Кожна грань опуклого політопа є опуклою множиною (політопом низької
розмірності). Якщо політом має вимірність d, то його d – 1 грані
називаються гіпергранями, d – 2 грані – підгранями, 1 – грані – ребрами,
0 – грані – вершинами. Для 3 політопа гіпергранями є плоскі
многокутники, а підграні та ребра співпадають. В цій термінології
порожня множина трактується як (-1) грань.

Означення. d політоп називається d симплексом, якщо він є опуклою
оболонкою (d + 1) афінно незалежних точок. Кожна підмножина з цих d
вершин є симплексом і є гранню. Кожна k грань містить 2k+1 граней
розмірностей k, k-1, k-2, …, 0, -1.

При d = 0, 1, 2, 3 відповідний симплекс є точкою, ребром, трикутником та
трикутною пірамідою.

Наприклад, трикутна піраміда (3 грань) містить одну 3 грань (сама
піраміда), чотири 2 грані (трикутники), шість 1 граней (ребра), чотири 0
граней (вершини) та одну (-1) грань (порожня множина), що разом складає
16 = 24 граней.

Означення. d політоп називається симпліциальним, якщо його кожна
гіпергрань є симплексом.

Задача 1. Опукла оболонка. В Ed задано множину S, що містить N точок.
Необхідно побудувати їх опуклу оболонку (повний опис границі CH(S)).

Задача 2. Крайні точки. В Ed задано множину S, що містить N точок.
Необхідно визначити ті з них, які є вершинами опуклої оболонки conv(S).

Задача 3. Перевірка крайності точок площини. На площині задано N точок.
Визначити, чи є вони вершинами своєї власної опуклої оболонки.

Теорема. Задача сортування зводиться за лінійний час до задачі побудови
опуклої оболонки. Для знаходження впорядкованих N точок опуклої оболонки
потрібен час O(N log N).

Доведення. Нехай дано N додатних дійсних чисел x1, x2, …, xN.
Поставимо у відповідність точці xi точку (xi, xi+1) і присвоємо їй номер
i. Утворені точки лежать на параболі y = x2. Опукла оболонка цієї
множини точок буде складатися зі списку точок множини, впорядкованому за
значенням абсциси.

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).

= Ѕ * (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-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 точки). Обрана множина містить не більш ніж 2k + 4 точок і позначимо
її через S*. Далі можна застосувати алгоритм Грехема побудови опуклої
оболонки для множини точок S*.

Приклад. Множину точок S розбито на k = 4 полоси. В кожній полосі обрано
дві точки. Для утвореної множини S* побудовано опуклу оболонку.

S, яка не попала всередину наближеної опуклої оболонки, знаходиться на
відстані, не більшої за значення (xmax – xmin) / k.

Швидкі методи побудови опуклої оболонки

Розіб’ємо множину S з N точок на дві підмножини, кожна з яких буде
містити одну з двох ламаних, об’єднання яких дає многокутник опуклої
оболонки. Початкове розбиття множини точок визначається прямою, що
проходить через дві точки l та r, які мають відповідно найменшу та
найбільшу абсцису. Позначимо через S1 підмножину точок, яка розташована
вище або на прямій, а через S2 – підмножину точок, яка розташована нижче
або на прямій. Якщо бути точним, то {S1, S2} не є розбиттям множини S,
оскільки {l, r} ??S1 ??S2. Далі множини S1 та S2 обробляються наступним
чином (розглянемо на прикладі множини S1).

Знайдемо точку h, для якої трикутник lhr має максимальну площу серед
усіх інших трикутників (якщо таких точок декілька, то обираємо ту, в
якій кут hlr більший). Точка h гарантовано належить опуклій оболонці.
Якщо провести через h пряму, паралельну lr, то над ній не буде жодної
точки множини S. Якщо на цій прямій лежать декілька точок, то згідно з
припущенням точка h буде самою лівою з них.

Будуємо дві прямі: L1 (сполучає точки l та h) та L2 (проходить через
точки h та r). Для кожної точки множини S1 визначаємо її положення
відносно цих прямих. Точки, які попали в трикутник lhr, можуть бути
вилучені з подальшої обробки. Жодна з точок не знаходиться зліва від L1
та зліва від L2 (напрямки прямих вказано на рисунку). Точки, розташовані
зліва від L1 чи на ній, утворюють множину S11. Аналогічно утворюється
множина S12. Утворені множини S11 та S12 передаються далі на наступний
рівень рекурсивної обробки.

Вибір початкових значень {l0, r0} точок l та r можна спростити. В якості
l візьмемо точку (x0, y0), яка має найменшу абсцису, а в якості r
візьмемо точку (x0, y0 – e), де e – мале додатне число. Вертикальна
пряма, що проходить через l, буде першою прямою, яка розбиває множину
точок S. Другою прямою буде пряма, що проходить через точки з
екстремальними абсцисами.

Через * далі позначено операцію конкатенації списків.

Швидка опукла оболонка (S, l, r)

if (S = {l, r}) then return (l, r) /* опукла оболонка складається з
єдиного орієнтованого ребра */

else

begin

h ??сама дальня точка(S, l, r);

S1 ??точки множини S, розташовані зліва від прямої lh чи на ній;

S2 ??точки множини S, розташовані зліва від прямої hr чи на ній;

return Швидка опукла оболонка (S1, l, r) * (Швидка опукла оболонка (S2,
h, r) – h);

end;

begin

l0 ??(x0, y0) ??точка множини S з найменшою абсцисою;

r0 ??(x0, y0 – e);

Швидка опукла оболонка (S, l0, r0);

видалити точку r0 /* це еквівалентно тому, якщо покласти e = 0 */

end.

Алгоритм типу розділяй та пануй

Припустимо, що при розв’язку задачі побудови опуклої оболонки початкова
множина точок S була розбита на дві частини S1 та S2, кожна з яких
містить половину точок множини S. Якщо тепер рекурсивно знайти CH(S1) та
CH(S2), то опуклу оболонку множини S можна знайти з рівності: CH(S1 ?
S2) = CH( CH(S1) ? CH(S2)). При цьому треба пам’ятати, що CH(S1) та
CH(S2) – це опуклі многокутники. Алгоритм розділяй та пануй має
наступний вигляд:

1. Якщо |S| ??k (k – невелике ціле число), то побудувати опуклу оболонку
одним із прямих методів та зупинитися; інакше перейти до кроку 2.

2. Розбити множину S довільним чином на дві приблизно рівні за
потужністю множини S1 та S2.

3. Рекурсивно знайти опуклі оболонки CH(S1) та CH(S2).

4. Злити дві отримані оболонки, утворивши CH(S).

Задача. Опукла оболонка об’єднання опуклих многокутників. Дано два
опуклих многокутника P1 та P2. Знайти опуклу оболонку їх об’єднання.

Алгоритм Шеймоса.

1. Знайти деяку внутрішню точку p многокутника P1 – наприклад, центроїд
трьох довільних вершин P1. Ця точка буде внутрішньою точкою CH(P1 ? P2).

2. Визначити, чи є p внутрішньою точкою P2. Якщо p не є внутрішньою
точкою P2, то перейти до кроку 4.

3. p є внутрішньою точкою P2. Вершини P1 та P2 є впорядкованими у
відповідності зі значенням полярного кута відносно точки p. За час O(N)
можна злити список вершин цих многокутників, отримавши впорядкований
список вершин як P1, так і P2. Перейти до кроку 5.

4. p не є внутрішньою точкою P2. Якщо дивитися з точки p, то многокутник
P2 лежить у кліні з кутом розвороту меншим чи рівним ?. Цей клин
визначається двома вершинами u та v многокутника P2, які можуть бути
знайдені за лінійний час за один обхід вершин многокутника P2. Ці
вершини розбивають границю P2 на два ланцюга вершин, які є монотонними
відносно зміни полярного кута з початком в p. При русі по одному ланцюгу
кут збільшується, при русі по другому – зменшується. Один з ланцюгів,
який є опуклим по напрямку до точки p, може бути видалений, оскільки
його вершини будуть внутрішніми точками CH(P1 ? P2). Другий ланцюг P2 та
границю P1 можна злити в один впорядкований список (за полярним кутом
відносно точки p) за лінійний час.

5. До отриманого впорядкованого списку вершин застосувати метод обходу
Грехема, який вимагає лінійний час.

Теорема. Опукла оболонка об’єднання двох опуклих многокутників може бути
знайдена за час, пропорційний сумарній кількості їх вершин.

Означення. Опорною прямою до опуклого многокутника називається пряма l,
яка проходить через деяку вершину многокутника P таким чином, що
внутрішня частина P цілком знаходиться по одну сторону від l.

Побічним результатом описаного метода злиття є знаходження опорних
прямих для двох опуклих многокутників. Два опуклих многокутника P1 та P2
з n та m вершинами відповідно, таких що один не лежить цілком всередині
іншого, мають не більш ніж 2 * min(n, m) опорних прямих. Якщо вже
отримано опуклу оболонку об’єднання P1 та P2, то опорні прямі
обчислюються в результаті перегляду списку вершин CH(P1 ? P2).

Теорема. Кожна пара послідовних вершин CH(P1 ? P2), одна з яких належить
P1, а друга P2, визначає опорну пряму.

Побудова опуклої оболонки простого многокутника

Алгоритм Лі. Нехай p1 – сама ліва вершина заданого простого многокутника
P, а (p1, p2, …, pN) – впорядкована циклічна послідовність його вершин
(за вершиною pN йде p1). Внутрішність P залишається по праву сторону при
обході його границі в указаному порядку. Нехай pM – сама права вершина.
p1 та pM є граничними точками опуклої оболонки многокутника P. Вони
розбивають послідовність вершин многокутника на два ланцюги: один від p1
до pM, другий – від pM до p1. Достатньо дослідити побудову опуклої
оболонки для ланцюга (p1, p2, …, pM), яку будемо називати верхньою
оболонкою.

Нехай (q1, q2, …, qR) – підпослідовність (p1, p2, …, pM), в якій q1
= p1 та qR = pM – шукана опукла оболонка многокутника. Кожне ребро
qiqi+1 є “кришкою кармана” Ki, де карман Ki – це ланцюг послідовності
(p1, p2, …, pM), першою та останньою вершинами якої є qi та qi+1
відповідно.

Алгоритм Лі проходить ланцюг та послідовно будує кришки усіх карманів.
Критичною будемо називати вершину, яка з останньою знайденою вершиною
типу q утворює карман. Але не кожна критична вершина належить кінцевій
опуклій оболонці. Кроком просунення будемо називати перехід від однієї
критичної вершини до іншої. Наприклад, на третьому кроці критичною
точкою є p4. Наступною критичною точкою буде p7. При цьому критична
точка p4 не належить опуклій оболонці.

1 крок 2 крок 3 крок 4 крок

M) і вершина ps = qi є критичною. Позначимо через u вершину границі Р,
яка є попередньою до qi. В залежності від положення u відносно
орієнтованого відрізка qMqi мають місце два випадки:

1. Вершина u знаходиться справа від qMqi або на ньому. Тоді треба
дослідити три області, які визначаються: прямою, що проходить через
точки qi-1 та qi; промінем, який є продовженням відрізку qiu та частиною
та частиною границі многокутника P, яка відповідає карману Ki-1.

2. Вершина u знаходиться зліва від qMqi. До дослідження треба додати
четверту область.

Позначимо через v вершину, яка йде за qi на границі многокутника P. Ця
вершина v може знаходитися в одній із областей, які визначено вище. В
областях 2 та 3 вершина v буде критичною, в інших – ні. Дослідимо
випадки розташування вершини v в кожній із цих областей.

Область 1. Границя многокутника заходить до карману. Рухаємося по
границі до тих пір, поки не досягнемо першого ребра границі, одна з
вершин w якого знаходиться зовні кармана (тобто в області 2). Це
обов’язково відбудеться, оскільки многокутник простий.

Область 2. Шукається опорна пряма з вершини v до ланцюга (q1, q2,
…,qi-1). Якщо ця пряма містить qr (r

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020