Сравнительный аналіз алгоритмів побудови опуклої оболонки на плоскости

Порівняльний аналіз алгоритмів побудови опуклої оболонки на плоскости.

Аннотация.

Тема даної курсової роботи — «Порівняльний аналіз алгоритмів побудови опуклої оболонки на площині «. Порівняйте взято чотири алгоритму: обхід методом Грехема, швидкий метод, метод «розділяй і пануй» та динамічний метод. Завдання цієї роботи — розкрити ці алгоритми і започаткувати дослідження ефективності їх. Програмна частина для курсової роботи виконано на Borland Delphi 4.

Оглавление Аннотация 2.

Введение

4.

Предварительная розробка алгоритму побудови опуклої оболонки 7.

Метод обходу Грехема 9.

Быстрые методи побудови опуклої оболонки. 11.

Алгоритмы типу «розділяй і владарюй». 12.

Динамические алгоритми побудови опуклої оболонки 14.

Сравнительный аналіз алгоритмів побудови опуклої оболонки 17.

Выводы 20.

Заключение

21.

Приложение Unit1. pas 22.

Литература

34.

Безліч різних завдань обчислювальної геометрії пов’язані з побудовою опуклої оболонки. Нині це завдання добре досліджували і має широке використання у розпізнаванні образов[i], обробці изображений[ii], а також у завдання у завданню розкроювання і компонування материала[iii]. Саме поняття опуклої оболонки є досить простою й інтуїтивно зрозумілим. Якщо уявити гумовий шнур, натягнутий силою-силенною точок, то це і буде опуклі оболонка для даного безлічі точок. Але, не дивлячись на свою простоту, він конструктивно, тому далі розглянуті способи налагодження ефективних алгоритмів для побудови опуклої оболонки. Оскільки алгоритми на вирішення нашої завдання, зазвичай, є подзадачами інших, складніших завдань, то цікаві лише алгоритми мають складність O (N log N). Саме поняття опуклої оболонки є досить простою й інтуїтивно зрозумілим. Якщо уявити гумовий шнур, натягнутий силою-силенною точок, то це і буде опуклі оболонка для даного безлічі точок. Але, не дивлячись на свою простоту, він конструктивно, тому далі розглянуті способи налагодження ефективних алгоритмів для побудови опуклої оболонки. Оскільки алгоритми на вирішення нашої завдання, зазвичай, є подзадачами інших, складніших завдань, то цікаві лише алгоритми мають складність O (N log N). Спочатку, кілька определений:

Визначення 1. Область D що належить простору E2, називатиметься опуклої, для будь-який пари точок q1 і q2 з D відрізок q1q2 повністю належить D.

Визначення 2. Опуклої оболонкою безлічі точок P. S, що належать простору E2, називається кордон найменшої опуклої області у E2, що охоплює S.

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

Визначення 3. Полиэдральным безліччю чи политопом називається те що кінцевого безлічі замкнутих полупространств.

Наступна теорема характеризує опуклі оболонки у властивому нам плане.

Теорему 1[iv]. Опуклі оболонка кінцевого безлічі точок в Ed є опуклим политопом. Навпаки, кожен опуклий политоп є опуклої оболонкою кінцевого безлічі точек.

Перш ніж переходити до опису алгоритмів слід зробити постановку завдань і побачити нижні оцінки вирішення її. Оскільки алгоритми мають працювати з кордоном опуклої оболонки безлічі L conv (L), то введемо нею позначення CH (L) і її також називати опуклої оболонкою. Сформулюємо дві основні задачи:

Завдання ВО1. (Опуклі оболонка). У E2 поставлено безліч P. S, що містить N точок. Потрібна побудувати їх опуклу оболонку (тобто. повне опис кордону CH (S)).

Завдання ВО2. (Відкритий алгоритм для опуклої оболонки). На площині задана послідовністю N точок p1, …, pN. Потрібна знайти опуклу оболонку в такий спосіб, щоб, після обробки точки pi була CH ({p1, …, pi}).

Розглянемо ВО1. Те, що вершини багатокутника, що є опуклої оболонкою, йдуть у порядку, свідчить про зв’язку з завданням сортування. У насправді, наступна теорема показує те, що рішення ВО1 має мати змогу виконати сортировку.

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

Доказ. Зведемо завдання сортування N позитивних дійсних чисел x1,., xN до завданню ВО1. Поставимо у відповідність числу xi точку (xi, xi2) і дамо їй номер і. Опуклі оболонка цього безлічі, подана у стандартному вигляді являтиме упорядкований щодо значення абсциссы безліч всіх точок з вихідного. З нього за лінійне час можна було одержати відсортований список.

Вочевидь, коли ми можемо вирішувати ВО2, ми можемо вирішити ВО1, поцьому завдання ВО1 можуть звести до ВО2 за лінійне час. Отже, нижня оцінка для ВО2 не нижче ((N log N).

Попередня розробка алгоритму побудови опуклої оболочки.

Спочатку розглянемо кілька малопродуктивних алгоритмів побудови опуклої оболочки.

Визначення 3. Крапка p опуклого безлічі P. S називається крайньої, а то й існує пари точок a, b (P.S таких, що p лежить на жіночих відкритому відрізку ab.

Вочевидь, що підмножина крайніх точок E є найменшим підмножиною P. S, опуклі оболонка якого, є опуклої оболонкою безлічі P. S, чи conv (E)=conv (S). Тож нас необхідне перебування опуклої оболонки виконати два кроку: Визначити крайні точки. Впорядкувати ці точки те щоб вони утворили опуклий многоугольник.

Теорему 3. Крапка p перестав бути крайньої точкою безлічі P. S тільки тоді ми коли він лежать у деякому трикутнику, вершинами якого належать P. S, але само собою воно перестав бути вершиною цього треугольника.

Ця теорема дає будувати алгоритм перевірки крайності точки. Якщо ми маємо справу з безліччю P. S потужності N, можна побудувати O (N3) трикутників. Перевірка приналежності точки трикутнику виконується за постійне кількість операцій. Отже, під час O (N3) можна визначити, чи є точка крайньої, а й за O (N4) і всіх точок. Наступна теорема показує, — у порядку повинні прагнути бути точки в кінцевому множестве.

Теорему 4. Послідовні вершини опуклого багатокутника вміщено у порядку, відповідному зміни кута відносно будь-якої внутрішньої точки.

Впорядкувати крайні точки безлічі можна щодо їх центроида. Центроид безлічі для N точок обчислюється під час O (N) арифметичних операцій. Грехем запропонував використовуватиме цього треба лише три будь-які неколлинеарные точки безлічі P. S. У разі це вимагатиме час O (N), але все перші трикрапку. Впорядкувати їх можна під час O (N log N). Отже, ми вирішуємо і завдання ВО1 під час O (N4).

Метод обходу Грэхема.

Наведений вище алгоритм є неефективним, тому необхідний спосіб швидшого побудови опуклої оболонки. І тому нам необхідний інший підхід. Грехем на одній із перших своїх робіт зумів показати, як і, попередньо отсортировав точки щодо полярного кута з центром в який-небудь внутрішньої точці, можна знайти крайні точки за лінійне время[v]. Нехай центр координат у якійсь внутрішньої точці. Впорядкуємо точки щодо полярного кута, і якщо такі збігаються щодо відстані від центру координат. Позаяк обидві точки лежать в одній прямий що проходить через центр координат, то тут для порівняння ми не маємо необхідності вираховуватимуть відстань, а можна порівняти суму абсолютних значень координат. Відсортовані точки слід розмістити у двусвязный список. Оскільки внутрішні точки належать деякому трикутнику (Opq), де p і q — сусідні вершини точці опуклої оболонки. Суть алгоритму в послідовному перегляді відсортованої списку та видаленні внутрішніх вершин. Решта точки будуть вершинами опуклої оболонки. Перегляд розпочнемо з точки що є вершиною ВО. І тому можна взяти точку з мінімальним абсциссой, і якщо слід їх дещо, те й мінімальної ординатою і позначити як початкову. Після цього, обходимо список, починаючи з неї, проти годинниковий стрілки і перевіряємо внутрішній кут для поточної точки. Якщо він більше або рівний (, то видаляємо вершину, а інакше переходимо до наступній. Оскільки кожний перегляд ми чи видаляємо одну вершину, чи переходимо до наступній, а перегляд закінчуємо під час досягнення вершини початок, яка піде, ми виконуємо трохи більше N кроків. Розглянутий метод називають методом обходу Грэхема.

Теорему 5. Опуклі оболонка N точок на площині можна знайти за час O (N log N) при пам’яті O (N) з допомогою лише арифметичних операцій та сравнений.

Доказ. З попереднього алгоритму видно, що він використовуються лише арифметичні операції, і порівняння. Для перебування внутрішньої точки в обхід потрібно лінійне час, але в сортування йде O (N log N). Для уявлення списку нам досить O (N) памяти.

Оскільки вище, було доведено, що нижня оцінка для алгоритму вирішального цю завдання дорівнює O (N log N), то отримуємо, що обхід Грехема має оптимальне час виконання. Але якого є оптимальним у разі, а поведінка їх у середньому ми вивчили. Цей алгоритм має низку недоліків. У ньому використовують тригонометрические функції, бо як їх обчислення пов’язані з великими витратами за часом, то бажано їх позбутися. Ендрю запропонував метод вирішення цієї проблемы[vi]. Коли площині задано N точок, що існує сама ліва та права крапки й є вершинами опуклої оболонки. Пряма, через ці точки ділить безліч на частини. Це точки, які лежать вищою, і точки, що від прямий. Обидва безлічі породжують відповідні їм частини опуклої оболонки, причому є монотонними ламаними щодо осі x. Тому, окремо отсортировав ці безлічі за значенням абсциссы, виробляється обхід Грехема. Недоліками алгоритму є і те, що не відкритий, а як і не допускає розбивка вихідної завдання на подзадачи для паралельної обработки.

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

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

[pic].

Рис. 1: h — сама віддалена від bl точка.

Суть алгоритму у тому, що вихідне безліч P. S з N точок розбивається на два підмножини, кожна з яких утримувати жодну з двох ламаних, які за поєднанні утворюють опуклу оболонку. Спочатку слід визначити дві точки, які будуть сусідніми вершинами опуклої оболонки. Можна взяти саму ліву вершину, нехай буде b, і саму ліву щодо b які залишилися, нехай буде e. Після цього потрібно знайти точку h максимально найвіддаленіші від прямий be. Усі крапки, що лежать в трикутнику bel виключають із подальшого розгляду. Інші точки ділитимуться на два підмножини: точки, які лежати лівіше bh і eh, і точки, що лежать правіше і bh, і eh. І з них містить ламані які у поєднані із e, b і h дають опуклу оболонку. З кожним із них проробляємо той самий. У підмножині точок P. S', лежачих лівіше bh і eh вибираємо h', максимально найвіддаленіші від eh, яка ділить його за частини. У тому числі одна викидається, інші ж діляться знову. Це реалізується рекурсивної процедурою, яка для даного їй безлічі повертає відповідну частку опуклої оболонки. Що стосується, коли потужність кожного, з підмножин, яким ділиться безліч, не перевершує деякою константи помноженою на потужність безлічі, отримуємо складність алгоритму, як й у швидкої сортування O (N log N). Однак у гіршому випадку може знадобитися час O (N 2).

Алгоритми типу «розділяй і властвуй».

У цьому алгоритмі, на відміну попереднього, безліч P. S розбивається на два равномощных підмножини P. S' і P. S'', та був рекурсивно будуються окремо оболонки кожного з неї і объединяются.

CH (S) = CH (S' (P.S'') = CH (CH (S') (CH (S'')).

Складність цього полягає у ефективному перебування поєднання двох випуклих оболонок. Наступний алгоритм злиття було запропоновано Шеймосом[vii]: Нехай ми маємо опуклі багатокутники P' і P''. Нам потрібно знайти P — їх злиття. Цього береться будь-яка внутрішня точка p для P' та перевіряється на приналежність P''. Якщо вона належить, то теоремі 4 маємо два упорядкованих щодо полярного кута до p безлічі. Протягом часу однакову сумі точок у яких ми можемо їх отримати один упорядкований список. Після чого, використовуючи обхід Грехема би за таке водночас отримати необхідний опуклий многоугольник.

[pic].

Рис. 2: Оскільки точка p всередині обох многоугольников, то вершини, як одного, і другого, упорядковані щодо полярного кута до p.

Що стосується, коли p не належить P'', доведеться знайти ліву праву опорні прямі з p до P'', pl і pr відповідно. Опорною прямий до опуклому многоугольнику P називатимемо пряму l, яка стелиться через деяку вершину цього багатокутника, в такий спосіб, що внутрішність P перебувають розслідування щодо один бік від l. І тому нам досить час O (N). Усі вершини P'' між l і r, на своєму шляху від l до r проти годинниковий стрілки, прибираємо з розгляду і виконуємо ті дії, які скоїли у разі принадлежности.

[pic].

Рис. 3: Оскільки точка p всередині одного багатокутника, то видаляємо все видимі з p вершини другого многоугольника.

Як бачимо, й у разі на злиття потрібен час O (N), де N — це загальна кількість точок в многоугольниках. Звідси випливає теорема:

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

Динамічні алгоритми побудови опуклої оболочки.

Усі наведені алгоритми є відкритими, оскільки вимагають спочатку знати всі крапки безлічі P. S. Однак у окремих випадках потрібно мати алгоритм здатний на час вступу нової точки змінювати опуклу оболонку. У разі ми маємо справу завдання ВО2. Вочевидь, що ухвалено рішення завдання існує. Можна щоразу після надходження точки використовувати обхід Грехема й одержати алгоритм зі складністю O (N2 log N), але хотілося б не давати у жертву оцінку O (N log N). І тому слід звернути увагу, що кожну новий кут алгоритм повинен або відкидати, чи вставляти його до списку точок їхнім виокремленням опуклу оболонку. Щоб самому отримати це оцінку, ми кожну точку повинні витрачати час O (log N), тобто повинна знаходити місце вставки і вставляти точку за O (log N). Такий алгоритм побудував Препарата[viii]. У цьому вся алгоритмі необхідно швидко знаходити опорні прямі до опуклому многоугольнику P і які відбуваються через деяку точку p. Після цього жодну з ланцюгів, куди розбивають опорні точки кордон опуклого багатокутника, замінити на p. Будемо називати опорну пряму pl лівої, якщо багатокутник P лежить справа від pl, і пряму pr правої, якщо зліва. Крапки l і r будемо називати опорними. Також будемо розрізняти увігнуті вершини, тобто. ті для яких відрізок, котрий поєднує їх і p, перетинає внутрішність багатокутника. А, які й увігнуті і опорні будуть опуклими. При перевірці якийсь вершини на увігнутість чи выгнутость ми можемо визначити, де шукати опорну точку. Тык ж ми повинен мати можливість швидко видалити ланцюжок вершин і вставити місце неї p. І тому ми мусимо зберігати багатокутник не писком, як це робилося у роки алгоритми, а AWL або іншими збалансованим деревом. У цьому вся дереві T перехід до лівого нащадку відповідатиме руху по годинниковий стрілці по опуклої оболонці, а правого проти годинниковий стрілки. До кожного вузла у тому дереві ми повинен мати можливість отримувати доступом до самої лівому вузлу. Якщо проаналізувати кореневої вузол дерева M і m — самий лівий вузол, всі вони розбивають кордон опуклого багатокутника на дві ланцюга, причому одна зберігається у лівій поддереве M, а друга правом. У залежність від типу вершини М і m, і навіть від цього, який кут (mpM) — лівий чи правий, можна накинути у якому поддереве перебуває опорна вершина. Розглянемо пошук лівої опорною вершини. Якщо (mpM) — лівий, а m — вігнуте чи те (mpM) — правий, а M — опуклі, то пошук ніжно продовжувати у лівій поддереве, інакше — у правому. Те саме і для правої опорною вершини. [pic][pic].

Рис. 4: Два варіанти m, M і p.

У такий спосіб ми бачимо під час O (log і) ліву праву опорні прямі. Після цього під час O (log і) ми можемо видалити все опуклі вершини і збалансуємо дерево. Звідси випливає теорема:

Теорему 7. Опуклі оболонка безлічі з N точок на площині то, можливо знайдено з допомогою відкритого алгоритму під час ((N log N) і з часом корекції ((log N).

Порівняльний аналіз алгоритмів побудови опуклої оболочки.

Оскільки теоретично показали, що час всіх алгоритмів загалом O (log N), слід очікувати під час тестування майже завжди результати відмінні на константу. Проведемо дослідження залежності часу роботи алгоритмів від розмірів завдання при рівномірному розподілі точек:

[pic].

Рис. 5: Залежність час виконання алгоритмів при рівномірному випадковому розташуванні точок (Nq^.y)) then begin e:=q; cut (q, e); ins (b, e); end else begin e:=p; cut (p, e); ins (b, e); end; end; if pnil then begin e:=p; inss (b, e, e^.prev); end; if qnil then begin e:=q; inss (b, e, e^.prev); end; end; procedure sort2(var b: prec;e:prec); var p, q: prec; x: tp; begin if b=e then exit; if b^.next=e then begin if (b^.xabs (t^.x-x)+abs (t^.y-y))) then r:=t; t:=t^.n; until t=l2; l2:=r; l1^.p^.n:=nil; l2^.p^.n:=nil; r:=l1; l:=l2; ls:=nil; while (rnil) and (lnil) do begin if (r^.a (m^.x-p^.x)*(m^.n^.y-p^.y))) then begin l:=m; exit; end; if (n^.n=n) or.

(((n^.n^.x-p^.x)*(n^.y-p^.y)=(n^.x-p^.x)*(n^.n^.y-p^.y)) and (abs (n^.x-p^.x)=abs (n^.n^.x-p^.x)+abs (n^.n^.x-n^.x)) and (abs (n^.yp^.y)=abs (n^.n^.y-p^.y)+abs (n^.n^.y-n^.y))) or.

(((n^.p^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.p^.y-p^.y)) and ((n^.n^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.n^.y-p^.y))) then begin l:=n; exit; end; if m^.nm then begin fm:=((m^.n^.x-p^.x)*(m^.y-p^.y)>(m^.x-p^.x)*(m^.n^.y-p^.y)) or.

((m^.p^.x-p^.x)*(m^.y-p^.y)(n^.x-p^.x)*(n^.n^.y-p^.y)) or.

((n^.p^.x-p^.x)*(n^.y-p^.y)(n^.x-p^.x)*(m^.y-p^.y);

if (m^.lnil) and ((f and not (fn)) or (not (f) and fm)) then getleft (m^.l, n, l) else if m^.rnil then getleft (m^.r, m^.n, l); end; end; procedure getright (m, n: prec;var l: prec); var fm, fn, f: boolean; begin l:=nil; if ((p^.x=m^.x) and (p^.y=m^.y)) or ((p^.x=n^.x) and (p^.y=n^.y)) then exit; if ((p^.x=m^.p^.x) and (p^.y=m^.p^.y)) or ((p^.x=n^.p^.x) and (p^.y=n^.p^.y)) then exit; if (m^.n=m) or.

(((m^.p^.x-p^.x)*(m^.y-p^.y)=(m^.x-p^.x)*(m^.p^.y-p^.y)) and (abs (m^.x-p^.x)=abs (m^.p^.x-p^.x)+abs (m^.p^.x-m^.x)) and (abs (m^.yp^.y)=abs (m^.p^.y-p^.y)+abs (m^.p^.y-m^.y))) or.

(((m^.p^.x-p^.x)*(m^.y-p^.y)m^.kl+1 then begin k:=m^.r; if k^.kl>k^.kr then k:=k^.l; if k^.u^.r=k then k^.u^.r:=k^.r else k^.u^.l:=k^.r; if k^.u^.r=k then k^.u^.kr:=k^.kr else k^.u^.kl:=k^.kr; if k^.rnil then k^.r^.u:=k^.u; r:=m^.r; kr:=m^.kr; m^.r:=k^.l; m^.kr:=k^.kl; if k^.lnil then k^.l^.u:=m; k^.r:=r; k^.kr:=kr; r^.u:=k; k^.l:=m; m^.u:=k; if unil then begin if u^.l=m then u^.l:=k else u^.r:=k; end else t:=k; k^.u:=u; balance (m, t, false); end; if f then balance (u, t, true); end;

procedure ins (m, d: prec); begin if m^.rnil then m^.r^.u:=d; d^.r:=m^.r; d^.l:=nil; d^.u:=m; m^.r:=d; balance (d, t, true);

end; procedure cutl (l:prec;var dl, dr: prec); var r, c: prec; begin r:=l; dl:=nil; if r^.lnil then begin dl:=r^.l; dl^.u:=nil; r^.l:=nil; r^.kl:=0; end; while rnil do begin c:=r^.u; if cnil then begin if c^.r=r then begin if c^.unil then begin if c^.u^.l=c then begin c^.u^.l:=r; r^.u:=c^.u; end else begin c^.u^.r:=r; r^.u:=c^.u; end; end else begin dr:=r; r^.u:=nil; end; c^.r:=dl; if dlnil then dl^.u:=c; dl:=c; dl^.u:=nil; continue; end; end; r:=r^.u; end; balance (l, dr, true); end; procedure cutr (r:prec;var dl, dr: prec); var l, c: prec; begin l:=r; dr:=nil; if l^.rnil then begin dr:=l^.r; dr^.u:=nil; l^.r:=nil; end; while lnil do begin c:=l^.u; if cnil then begin if c^.l=l then begin if c^.unil then begin if c^.u^.l=c then begin c^.u^.l:=l; l^.u:=c^.u; end else begin c^.u^.r:=l; l^.u:=c^.u; end; end else begin dl:=l; l^.u:=nil; end; c^.l:=dr; if drnil then dr^.u:=c; dr:=c; dr^.u:=nil; continue; end; end; l:=l^.u; end; balance (r, dl, true); end; procedure add (p:prec); var l, r, d:prec; begin getleft (t, n, l); if lnil then begin getright (t, n, r); if (n=r) or ((n^.x-r^.x)*(l^.y-r^.y)timew; str ((now-time)/kkk*24*60*60:0:6,strr);

TimeL.Caption:=strr+ «p.s » ;

PaintBox1.Refresh; end; procedure TForm1. Button1Click (Sender: TObject); begin while snnil do begin tt:=sn^.n; dispose (sn); sn:=tt; end; while cnnil do begin tt:=cn^.n; dispose (cn); cn:=tt; end; halt; end; procedure TForm1. Button3Click (Sender: TObject); var i: integer; t: pr; begin randomize (); while cnnil do begin t:=cn^.n; dispose (cn); cn:=t; end; while snnil do begin t:=sn^.n; dispose (sn); sn:=t; end; mx:=0; my:=0; new (t); t^.n:=cn; cn:=t; t^.x:=0; t^.y:=10; if mx.