- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Приклад3
Тема: Алгоритми побудови опуклої оболонки
Задача побудови опуклої оболонки не тільки є центральною в великій кількості прикладних задач, а і дозволяє розв’язати ряд питань обчислювальної геометрії, що на перший погляд здаються непов’язаними з нею. Побудова скінченої множини точок, особливо у випадку точок на площині, достатньо широко і глибоко досліджена і використовується, наприклад, при обробці зображень, розпізнаванні образів, в задачах розкрою та компановки матеріалів.
Поняття опуклої оболонки множини точок S є природним і простим. У відповідності з означенням це найменша опукла множина, що вміщує S. Але таке означення не є конструктивним, не дивлячись на інтуїтивну ясність і простоту. Тому слід попередньо ввести деякі поняття і означення, що сприяли розробці алгоритмів побудови опуклих оболонок.
Опукла оболонка
Означення. Афінна геометрія складається з множини скалярів 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. Опукла оболонка цієї множини точок буде складатися зі списку точок множини, впорядкованому за значенням абсциси.
Означення.
Точка 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.
