Otoczka wypukła
01.12.2011 - Michał Karpiński
O przypadkach zdegenerowanychZanim 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 , to krok zostanie wykonany poprawnie, bo porównanie punktów i nie zmieni stanu zmiennej . Jednak jeśli pierwszym kandydatem będzie , to ostateczne rozwiązanie będzie niepoprawne. Zauważmy, że w następnym kroku wzięlibyśmy 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 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: i . 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 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 GrahamaW 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 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ą ) wyznaczamy w prosty sposób: bierzemy punkt, który znajduje się najbardziej na dole (czyli taki, który ma najmniejszą współrzędną ), a jeśli takich punktów jest kilka, to wybieramy ten najbardziej na lewo (czyli taki, który ma najmniejszą współrzędną ). Nie trudno zauważyć, że punkt startowy będzie częścią otoczki. Punkt startowy ustawiamy na początku zbioru (). Sortujemy tablicę kątowo względem . Oznacza to, że pierwszym elementem zbioru ma być punkt, który tworzy najmniejszy kąt z punktem i prostą równoległą do osi przechodzącą przez (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 ), 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 . 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 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com