Otoczka wypukła

01.12.2011 - Michał Karpiński
TrudnośćTrudność

O przypadkach zdegenerowanych

Zanim poznamy następną metodę wyznaczającą otoczkę wypukłą chciałbym przekazać wszystkim bardzo smutną nowinę. Otóż okazuje się, że jeśli zapisalibyśmy procedurę z poprzedniej strony w jakimkolwiek języku programowania, to nie będzie ona działać poprawnie (przynajmniej nie dla wszystkich zestawów danych).

Dzieje się tak dlatego, że podczas zapisywania procedury w pseudokodzie pominęliśmy tzw. przypadki zdegenerowane. Trudno jest precyzyjnie zdefiniować czym tak właściwie są przypadki zdegenerowane. W algorytmach rozwiązujących problemy geometryczne są to pewne specyficzne ustawienia punktów, odcinków, prostych, figur itp. Takie ustawienia sprawiają, że struktury danych lub techniki użyte w algorytmach geometrycznych źle interpretują część danych wejściowych co prowadzi do katastrofy.

Gdzie w algorytmie Jarvisa możemy wpaść w pułapkę? Zastanówmy się, jak działałby nasz algorytm, w sytuacji gdy trzy kolejne punkty otoczki leżałyby na jednej prostej. Załóżmy, że jesteśmy w jakimś momencie wykonywania obliczeń, znaleźliśmy następny punkt otoczki, wracamy do początku pętli zewnętrznej i napotykamy na sytuację z rysunku obok.Wchodzimy do pętli wewnętrznej. Jeśli jako pierwszy na kandydata zostanie wybrany punkt $ p_2 $, to krok zostanie wykonany poprawnie, bo porównanie punktów $ p_1 $ i $ p_2 $ nie zmieni stanu zmiennej $ nastepnyPunkt $. Jednak jeśli pierwszym kandydatem będzie $ p_1 $, to ostateczne rozwiązanie będzie niepoprawne. Zauważmy, że w następnym kroku wzięlibyśmy $ p_2 $ do otoczki i oba te punkty należałyby do wyniku. Kłóci się to z definicją otoczki wypukłej. Chcemy aby wielokąt zawierający wszystkie punkty był najmniejszy nie tylko w sensie pola powierzchni, ale także ilości boków.

Punkt $ p_1 $ powinien zostać pominięty w rozwiązaniu. Jak sobie z tym poradzić? Każdy pewnie zna wzór na odległość dwóch punktów na płaszczyźnie. Wystarczy użyć tego wzoru gdy napotkamy na sytuację, gdy dwa kolejne punkty wraz z ostatnio znalezionym punktem otoczki leżą na jednej prostej. Sprawdzamy odległość dwóch następnych kandydatów od ostatnio dodanego punktu otoczki, czyli porównujemy ze sobą długość dwóch odcinków: $ \{CH[i],p_1\} $ i $ \{CH[i],p_2\} $. Dłuższy odcinek wygrywa, a jego koniec zostaje nowym kandydatem na następny punkt otoczki.

Podsumowując: jedyne co trzeba zrobić, to dodać jeszcze jeden warunek do pętli wewnętrznej sprawdzający czy funkcja $ NA{-}LEWO $ zwróciła warość zero. Myślę, że każdy z łatwością poradzi sobie z wprowadzeniem odpowiednich modyfikacji.

Pozostaje jeszcze jedna kwestia: dlaczego od razu nie zapisaliśmy tego warunku w pseudokodzie? Odpowiedź: ponieważ łatwiej jest nam myśleć o idei algorytmu używając ougólnionych danych. Gdybyśmy od razu zaczęli wymyślać jakieś złośliwe dane i na bierząco starać się z nimi walczyć, to w końcu byśmy się w tym wszystkim pogubili i zrobiłoby się nam smutno. Co prawda w algorytmie Jarvisa nie ma trudności z przypadkami zdegenerowanymi, ale im bardziej wgłębiamy się w świat geometrii obliczeniowej, tym więcej napotykamy algorytmów, gdzie przypadki brzegowe i zdegenerowane występują w takiej ilości, że zaczyna boleć głowa.

Na zakończenie tego działu, dobra rada: myślmy ogólnie, myślmy prościej :)

Algorytm Grahama

W tym rozdziale omówimy bardziej efektywny algorytm znajdowania otoczki wypukłej. Jest on w większości przypadków znacznie szybszy od metody pakowania prezentu i czas jego działania nie zależy od rozmiaru wyniku. Jedyne co wzrośnie, to poziom skomplikowania, ale tylko nieznacznie. Tak jak pakowanie prezentu, algorytm Grahama jest również jednym z popularniejszych rozwiązań problemu otoczki wypukłej.

W algorytmie Grahama - zanim przystąpimy do właściwego wyznaczania rozwiązania – dane muszą być wcześniej odpowiednio przygotowane. Mianowicie, wszystkie punkty ze zbioru $ P $ muszą zostać posortowane i to nie w byle jaki sposób. Otóż punkty sortować będziemy kątowo względem punktu startowego.

Punkt startowy (oznaczony literą $ S $) wyznaczamy w prosty sposób: bierzemy punkt, który znajduje się najbardziej na dole (czyli taki, który ma najmniejszą współrzędną $ y $), a jeśli takich punktów jest kilka, to wybieramy ten najbardziej na lewo (czyli taki, który ma najmniejszą współrzędną $ x $). Nie trudno zauważyć, że punkt startowy będzie częścią otoczki.

Punkt startowy ustawiamy na początku zbioru $ P $ ($ P[1] = S $). Sortujemy tablicę $ P[2..n] $ kątowo względem $ P[1] $. Oznacza to, że pierwszym elementem zbioru $ P[2..n] $ ma być punkt, który tworzy najmniejszy kąt z punktem $ P[1] $ i prostą równoległą do osi $ OX $ przechodzącą przez $ P[1] $ (patrz rysunek powyżej).

Do sortowania można wykorzystać jakąkolwiek znaną metodę np. quicksort, heapsort lub margesort. Ważne, aby sortownie przebiegało jak najszybciej (najlepiej w $ O(n \log n) $), bo jak się później okażę, w algorytmie Grahama sortowanie zabiera najwięcej czasu i dominuje czas właściwego wyznaczania otoczki.

Zachodzi pytanie: jak wyznaczyć te wszystkie kąty? Ja proponuję zadać inne pytanie: czy w ogóle trzeba je wyznaczyć? Okazuje się, że nie. Zauważmy, że wartość każdego z kątów należy do przedziału $ [0^o,180^o) $. Wynika to z wyboru punktu startowego. Teraz wystarczy przypomnieć sobie z lekcji matematyki, że funkcja cosinus jest monotoniczna właśnie w tym przedziale, a wyznaczenie cosinusa z szukanego kąta jest o wiele prostsze, bo wymaga tylko kilku operacji arytmetycznych. Wyszperanie odpowiednich wzorów z licealnych (a nawet gimnazjalnych) książek pozostawiam czytelnikowi.

Mając posortowane punkty można wreszcie przejść do sedna naszego algorytmu.

5
Twoja ocena: Brak Ocena: 5 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com