Otoczka wypukła

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

Metoda pakowania prezentu cd.

Mamy dany zbiór punktów $ P $. Zamiast patrzeć na całą otoczkę spójrzmy jedynie na którąkolwiek z krawędzi, która do niej należy. Taka krawędź łączy dwa punkty, które nazwiemy $ p $ i $ q $. Łatwo jest dostrzec, że wszystkie inne punkty ze zbioru $ P $ muszą: albo leżeć na krawędzi $ \{p,q\} $, albo znajdować się po jednej stronie prostej $ l $, którą wyznaczają punkty $ p $ i $ q $. Twierdzenie odwrotne również zachodzi. Podsumowując:

Krawędź $ \{p,q\} $ należy do otoczki wypukłej wtedy i tylko wtedy, gdy wszystkie inne punkty leżą na lub po jednej ze stron tej krawędzi.

Teraz widać, że pakowanie prezentu rzeczywiście wyznacza otoczkę wypukłą, gdyż kolejne krawędzie dołączane do otoczki spełniają powyższy warunek.

Pseudokod

Pora przedstawić procedurę, która odwzorowuję naszą intuicję o pakowaniu prezentu. Nie będziemy jednak fizycznie tworzyli półprostej obracającej się wokół własnej osi. Takie podejście jest nieefektywne i niepoprawne. „Pakowanie” to tylko sposób myślenia o rozwiązaniu naszego problemu. W rzeczywistości do odkrywania kolejnych punktów otoczki posłużymy się twierdzeniem z poprzedniego akapitu. Przeanalizujmy poniższy algorytm:

Oto znaczenie zmiennych i struktur użytych w procedurze $ JARVIS{-}HULL $:

  • $ P[1..n] $ – tablica punktów płaszczyzny podanych na wejściu
  • $ CH[1..n] $ – tablica, w której przechowywane są kolejne punkty należące do otoczki wypukłej. Wielkość tej tablicy to $ n $, ponieważ może się zdarzyć, że każdy punkt z $ P $ należy do otoczki (w większości przypadków będzie ich znacznie mniej).
  • $ punktOtoczki $ – jest to zmienna przechowująca punkt, który na pewno znajdzie się w otoczce.
  • $ nastepnyPunkt $ – zmienna pomocnicza, która przechowuje kandydatów na kolejny punkt otoczki

Algorytm działa następująco:

1. Wyznaczamy punkt startowy. Jest to taki punkt ze zbioru $ P $, który na pewno znajdzie się w rozwiązaniu. Nie ma chyba żadnych wątpliwości, że punkt, który znajduje się najbardziej na prawo spełnia nasze założenia. Przypisujemy ten punkt do zmiennej $ punktOtoczki $. Kolejnych punktów otoczki będziemy szukali zgodnie z ruchem wskazówek zegara.

2. Wchodzimy w pętle zewnętrzną. Dodajemy znaleziony punkt otoczki do rozwiązania.

3. Szukamy następnego punktu otoczki, który będziemy przechowywać w zmiennej $ nastepnyPunkt $. Teraz najważniejsze: chcemy, aby kolejny punkt wraz z ostatnio znalezionym punktem otoczki utworzyli krawędź skierowaną $ \{ CH[i], nastepnyPunkt \} $ taką, że wszystkie inne punkty ze zbioru $ P $ leżą na prawo od niej. Taki punkt można wyznaczyć w bardzo prosty sposób. Najpierw do zmiennej $ nastepnyPunkt $ przypisujemy pierwszy element zbioru $ P $. W pętli wewnętrznej sprawdzamy kolejne elementy zbioru $ P $. Jeśli zdarzy się, że w $ j $-tej iteracji punkt $ P[j] $ znajduje się na lewo od krawędzi $ \{ CH[i], nastepnyPunkt \} $, to aktualizujemy zmienną $ nastepnyPunkt $ przypisując jej nową wartość: $ P[j] $. Aby wykonać tego sprawdzenia posłużymy się pomocniczą procedurą $ NA{-}LEWO(a,\{b,c\}) $, która wyznacza, po której stronie krawędzi $ \{b,c\} $ znajduje się punkt $ a $. Po opuszczeniu pętli w zmiennej $ nastepnyPunkt $ znajdować się będzie kolejny punkt należący do otoczki wypukłej. Wartość tą przypisujemy zmiennej $ punktOtoczki $.

Mała dygresja: warto zauważyć, że wyznaczenie kolejnego punktu otoczki jest bardzo podobne do szukania największego elementu ze zbioru liczb. Najpierw przyjmujemy, że największym element jest pierwszy ze zbioru. Następnie przechodzimy od lewej do prawej cały zbiór i aktualizujemy naszego "maxa", jeśli któryś z elementów jest od niego większy. W algorytmie Jarvisa zbiór liczb zamieniamy na zbiór punktów, a relację "mniejszy-równy" na relację "na-lewo-od".

4. Jeśli następny punkt otoczki jest za razem pierwszym, to algorytm się kończy. W przeciwnym razie wracamy do kroku 2.

Poprawność algorytmu wynika wprost z udowodnionego wcześniej twierdzenia.

O procedurze NA-LEWO

W naszym algorytmie wykorzystaliśmy pomocniczą funkcję $ NA{-}LEWO $, która dla danego punktu i skierowanego odcinka sprawdzała, po której stronie odcinka leży ten punkt. Oto definicja tej funkcji:

$ NA{-}LEWO(a,\{b,c\}) = (c_X - b_X)(a_Y - b_Y) - (a_X - b_X)(c_Y - b_Y) $

Jeśli zwrócona wartość jest:

  • większa od zera, to punkt $ a $ leży na lewo od odcinka $ \{b,c\} $
  • mniejsza od zera, to punkt $ a $ leży na prawo od odcinka $ \{b,c\} $
  • równa zero. Oznacza to, że punkty $ a $, $ b $ oraz $ c $ są współliniowe (czyli leżą na jednej prostej). Ten przypadek omówimy osobno na następnej stronie.

Mała uwaga: jeśli nie jesteś do końca przekonany, że powyższy wzór jest poprawny, to polecam przeczytanie artykułu pt. "Krótki wstęp do algorytmów geometrycznych".

Złożoność czasowa

Algorytm Jarvisa jest na tyle prosty, że nie będziemy mieli problemów z analizą jego złożoności. Zauważmy, że wewnętrzna pętla przebiega po wszystkich $ n $ punktach, a zewnętrzna pętla wykona się dokładnie tyle razy, ile punktów leży na otoczce wypukłej. Podsumowując, jeśli oznaczymy liczbę punktów otoczki jako $ h $, to dokładnie $ h $ razy będziemy musieli przejrzeć tablicę rozmiaru $ n $. Z tego wniosek, że złożoność czasowa algorytmu pakowania prezentu to $ O(nh) $.

Zwróćmy uwagę na to, że czas jest zależny od wyniku. Nie jesteśmy w stanie przewidzieć wartości $ h $ przed uruchomieniem procedury $ JARVIS{-}HULL $, chociaż w niektórych przypadkach można dokonać pewnych oszacowań, ale to już zależy od rozwiązywanego problemu. Czy warto więc stosować algorytm Jarvisa? Na pewno wielką zaletą jest jego prosta idea i łatwość implementacji. Należy jednak pamiętać, że dla pewnych złośliwych danych (np. gdy wszystkie punkty leżą na obwodzie koła) czas działania może wynieść nawet $ O(n^2) $.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com