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

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

Припустимо, що при розв’язку задачі побудови опуклої оболонки початкова множина точок 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, визначає опорну пряму.

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