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

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

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

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

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

 
 

Цікаве