Анотація
Тема даної курсової роботи - " Порівняльний аналіз алгоритмів побудови опуклої оболонки на площині ". Для порівняння взяті чотири алгоритму: обхід методом Грехема, швидкий метод, метод "Розділяй і владарюй "і динамічний метод. Завдання цієї роботи - Розкрити ці алгоритми та провести дослідження ефективності їх.
Програмна частина для курсової роботи виконана на Borland Delphi 4.
Зміст
Анотація 2
Введення 4
Попередня розробка алгоритму побудови опуклої оболонки 7
Метод обходу Грехема 9
Швидкі методи побудови опуклою оболонки. 11
Алгоритми типу "розділяй і володарюй ". 12
Динамічні алгоритми побудови опуклої оболонки 14
Порівняльний аналіз алгоритмів побудови опуклої оболонки 17
Висновки 20
Висновок 21
Додаток Unit1.pas 22
Література 34
Введення
Безліч різних завдань обчислювальної геометрії пов'язане з побудовою опуклої оболонки. У справжній момент ця завдання добре досліджена і має широке застосування в розпізнаванні образів 1 , обробці зображень 2 , а так само в задачах в задачі розкрою і компонування матеріалу 3 .
Саме поняття опуклої оболонки є досить простим і інтуїтивно зрозумілим. Якщо представити гумовий шнур, натягнутий на безліч точок, то це і буде опукла оболонка для даної множини точок. Але, не дивлячись на свою простоту, воно не конструктивно, тому далі будуть розглянуті способи побудови ефективних алгоритмів для побудови опуклої оболонки. Так як алгоритми для вирішення нашої задачі, як правило, є подзадачами інших, більш складних завдань, то інтерес являють тільки алгоритми мають складність O ( N log N ).
Саме поняття опуклої оболонки є досить простим і інтуїтивно зрозумілим. Якщо представити гумовий шнур, натягнутий на безліч точок, то це і буде опукла оболонка для даної множини точок. Але, не дивлячись на свою простоту, воно не конструктивно, тому далі будуть розглянуті способи побудови ефективних алгоритмів для побудови опуклої оболонки. Так як алгоритми для вирішення нашої задачі, як правило, є подзадачами інших, більш складних завдань, то інтерес являють тільки алгоритми мають складність O ( N log N ).
Для початку, кілька визначень:
Визначення 1 . Область D приналежна простору E 2 , буде називатися опуклою , якщо для будь пари точок q 1 і q 2 з D відрізок q 1 q 2 цілком належить D.
Визначення 2 . Опуклою оболонкою безлічі точок S , що належать простору E 2 , називається межа найменшою опуклої області в E 2 , яка охоплює S .
Далі будемо мати справу тільки з множинами, складаються з кінцевого числа точок. Тому щоб охарактеризувати структуру опуклої оболонки нам потрібно узагальнити поняття опуклого багатокутника.
Визначення 3 . Поліедральних безліччю або політопом називається перетин кінцевого безлічі замкнутих півпросторів.
Наступна теорема характеризує опуклі оболонки в потрібному нам плані.
Теорема 1 4 . Опукла оболонка кінцевого безлічі точок в E d є опуклим політопом. Навпаки, кожен опуклий політоп є опуклою оболонкою кінцевого безлічі точок.
Перш ніж переходити до опису алгоритмів слід провести постановку задач і визначити нижні оцінки для вирішення їх. Так як алгоритми мають справу з кордоном опуклою оболонки безлічі L conv ( L ), то введемо для неї позначення CH ( L ) і будемо її також називати опуклою оболонкою.
Сформулюємо дві основні завдання:
Завдання ВО1. (Опукла оболонка). У E 2 задано безліч S , містить N точок. Вимагається побудувати їх опуклу оболонку (Тобто повний опис кордону CH ( S )).
Завдання ВО2. (Відкритий алгоритм для опуклої оболонки). На площині задана послідовність з N точок p 1 , ..., P N . Потрібно знайти опуклу оболонку таким чином, щоб, після обробки точки p i малася CH ({ p 1 , ..., P i }).
Розглянемо ВО1. Те, що вершини багатокутника, є опуклою оболонкою, слідують в визначеному порядку, вказує на зв'язок із завданням сортування. У самому справі, наступна теорема показує те, що рішення ВО1 повинно бути в стані виконати сортування.
Теорема 2 . Задача сортування за лінійний час зводиться до задачі побудови опуклої оболонки, і, отже, для знаходження впорядкованої опуклої оболонки для N точок на площині потрібен час пЃ— ( N log N ) .
Доказ . Зведемо задачу сортування N позитивних дійсних чисел x 1 , .., x N до задачі ВО1. Поставимо у відповідність числу x i точку ( x i , x i 2 ) і присвоїмо їй номер i . Опукла оболонка цієї множини, представлена в стандартному вигляді буде представляти собою впорядковану щодо значення абсциси множина всіх точок з вихідного. З нього за лінійний час можна отримати відсортоване список.
Очевидно, що якщо ми можемо вирішувати ВО2, то ми можемо вирішити і ВО1, по-цьому завдання ВО1 може бути зведена до ВО2 за лінійний час. Отже, нижня оцінка для ВО2 не нижче пЃ— ( N log N ).
Попередня розробка алгоритму побудови опуклої оболонки
Для початку розглянемо кілька малопродуктивних алгоритмів побудови опуклої оболонки.
Визначення 3 . Точка p опуклого безлічі S називається крайньої , якщо не існує пари точок a , b пѓЋ S таких, що p лежить на відкритому відрізку ab .
Очевидно, що підмножина крайніх точок E є найменшим підмножиною S , опукла оболонка якого, є опуклою оболонкою безлічі S , або conv ( E ) = conv ( S ). Тому нам необхідно для знаходження опуклої оболонки виконати дві кроку:
Визначити крайні точки.
Упорядкувати ці точки так, щоб вони утворили опуклий багатокутник.
Теорема 3 . Точка p НЕ є крайньою точкою безлічі S тільки тоді коли вона лежить в деякому трикутнику, вершинами якого належать S, але сама вона не є вершиною цього трикутника.
Ця теорема дає можливість побудувати алгоритм перевірки крайності точки. Якщо ми маємо справу з безліччю S потужності N , то можна побудувати O ( N 3 ) трикутників. Перевірка приналежності точки трикутнику виконується за постійне кількість операцій. Отже, за час O ( N 3 ) можна визначити, чи є точка крайньою, а за O ( N 4 ) і для всіх точок.
Наступна теорема показує, - В якому порядку повинні бути точки в кінцевому множині.
Теорема 4 . Послідовні вершини опуклого багатокутника розташовуються в порядку, відповідному зміні кута щодо будь внутрішньої точки.
Упорядкувати крайні т...
