algorytm.org

Znajdowanie wypukłej otoczki (algorytm Grahama)



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Znajdowanie wypukłej otoczki (algorytm Grahama)
Ocena użytkowników:***** / 48
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 03 sierpnia 2005 22:24

Wypukła otoczka zbioru punktów Q to najmniejszy wypukły wielokąt taki, że każdy punkt ze zbioru Q leży albo na brzegu wielokąta albo w jego wnętrzu.
Oto przykład:
Image
Jak widać otoczka składa się z 6 wierzchołków, jest to najmniejszy podzbiór zbioru Q taki że ich ciąg tworzy otoczkę zbioru Q.
Przeanalizujemy teraz algorytm Grahama, zakładamy przy tym, że zbiór Q jest uporządkowany w następujący sposób:
  1. wierzchołek o najmniejszym indeksie (u nas a) ma najmniejszą wartość y (jeśli jest kilka wierzchołków o najmniejszej wartości y, wybieramy skrajnie lewy)
  2. kolejne wierzchołki (u nas b do j) są posortowane ze względu na kąt nachylenia ich wektorów wodzących do osi X
Takie uporządkowanie możemy otrzymać za pomocą algorytmu porządkowania wierzchołków.
Na poniższym rysunku widać proste zawierające wektory wodzące punktów, z kątów których wynika przyjęty porządek:
Image
Punkt a ze względu na swe położenie jest oczywiście pierwszym wierzchołkiem otoczki. Algorytm Grahama polega na przechodzeniu do kolejnych wierzchołków z posortowanej listy, umieszczaniu ich na stosie i sprawdzaniu kierunku, w którym nastąpiło to przejście:
  1. jeżeli odchylenie nastąpiło w prawą stronę, zdejmowany jest wierzchołek ze stosu
  2. jeżeli odchylenie nastąpiło w stronę lewą, wierzchołek pozostaje na stosie
Oto algorytm zapisany w pseudokodzie:
Niech S1 oznacza element na szczycie stosu a S2 element pod nim
m- liczba punktów
pi (i=0...m) oznacza i-ty punkt z uporządkowanej listy (w analogii do rysunku: p0=a, p1=b itd...) K oznacza kąt między punktami S2, S1 oraz pi
  1. Umieść na stosie punkty p0, p1 i p2
  2. for i=3 to m do {
  3.   while K oznacza skręt w prawo
  4.       do Usuń punkt ze stosu
  5.   Dodaj na stos punkt pi
  6. }
Jak widać kluczową czynnością w algorytmie jest określanie kierunku, w którym przechodzimy do następnego punktu. Można do tego celu wykorzystać metodę wyznaczników (opisaną w algorytmie współliniowości trzech punktów). Będziemy brać pod uwagę dwa wektory zaczepione we wspólnym punkcie.

Image Np. zał. że na szczycie stosu mamy punkt b a tuż pod nim punkt a. Kolejnym punktem do przeanalizowania jest punkt c, chcemy sprawdzić, czy przechodząc do tego punktu (z punktu b) skręcimy w lewo, czy w prawo. Tworzymy więc dwa wektory AB oraz AC (zob. rysunek). Następnie za pomocą wyznaczników sprawdzamy po której stronie wektora AB leży punkt c. W przykładzie z rysunku wyznacznik det(a,b,c)>0 (gdyż punkt c leży po lewej stronie wektora). A zatem przechodząc z punktu b do punktu c skręcimy w lewo.




Przeanalizujemy teraz kilka kroków algorytmu, dany jest uporządkowany ciąg punktów:
Image
Wykonujemy pierwszy punkt algorytmy S={a, b, c} (zawartość stosu na rysunku jest oznaczona jako ciąg wierzchołków wyznaczający łamaną) i inicjujemy zmienną i=3 (m=9):
Image
sprawdzamy, po której stronie wektora BC znajduje się punkt wskazany przez zmienną i=3 (pamiętajmy, że liczymy od 0) a więc det(b,c,d). Z rysunku widać, że punkt ten leży po prawej stronie, więc obliczony wyznacznik będzie miał wartość ujemną. A zatem przechodząc przez ten punkt skręcimy w prawo. zgodnie z punktem 4. algorytmu usuwamy jeden punkt ze stosu: S={a,b}
Image
Sprawdzamy więc, po której stronie wektora AB (gdyż C usunęliśmy) leży punkt d (zmienna i nadal ma wartość 3). Obliczymy, że det(a,b,d)>0, a więc skręcamy w lewo zatem dodajemy punkt d na stos i inkrementujemy zmienną (i++).
Image
Zmienna i wskazuje na punkt e, na szczycie stosu mamy punkty d i b, zatem obliczamy det(b,d,e), otrzymujemy wartość ujemną, co oznacza skręt w prawo. Zdejmujemy więc wierzchołek ze stosu, czyli S={a, b}:
Image
badamy det(a,b,e) i otrzymujemy wartość dodatnią, dodajemy wierzchołek e na stos (S={a,b,e}) i inkrementujemy zmienną i.
Image
Postępując tak aż do momentu, gdy m osiągnie wartość 9 otrzymamy na stosie ciąg wierzchołków tworzących wypukłą otoczkę. Dla pełnej jasności przedstawię jeszcze na rysunku przebieg kolejnych kroków:
Image

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał KnasieckiC/C++
.cpp
.cpp
***** / 9
Emil HotkowskiC/C++Graham + Sortowanie kątowe
.cpp
.cpp
***** / 7
Jakub KoniecznyJava_Blockuproszczona metoda
.jbf
.jbf
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 20 czerwca 2011 21:36
Komentarze
photo
+1 # bogdan 2010-02-03 14:26
Zgodnie z opisem algorytmu w pseudokodzie punkt p[m] zawsze zostanie na stosie.
A niekiedy nie powinien.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Павле 2011-01-12 17:57
„jeżeli odchylenie nastąpiło w prawą stronę, zdejmowany jest wierzchołek ze stosu
jeżeli odchylenie nastąpiło w stronę lewą, wierzchołek pozostaje na stosie”

To bardzo niejasny fragment, dużo łatwiej by szło zrozumieć gdyby kryterium nie był „skręt w lewo / prawo”, tylko różnica odległości aktualnego i poprzedniego punktu od a (czyli dla a=(0,0) to będzie długość wektora wyznaczającego punkty p_i i p_i-1)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Maciej Stys 2012-05-20 15:45
Niestety ale program wykonany przez p. Knasieckiego posiada blad wykonania przy pkt 0,1 1,1 2,3 2,-1 4,1 8,-1. niestety nie moge go znalesc. co najdziwniejsze wpisane od tylu daja inny wynik.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Mariusz_ 2019-11-27 00:50
Cytuję Maciej Stys:
Niestety ale program wykonany przez p. Knasieckiego posiada blad wykonania przy pkt 0,1 1,1 2,3 2,-1 4,1 8,-1. niestety nie moge go znalesc. co najdziwniejsze wpisane od tylu daja inny wynik.


Nic dziwnego skoro p. Knasiecki myli
układ biegunowy z kartezjańskim

Punkty powinny zostać posortowane względem miar kątów nachylenia do osi biegunowej, natomiast punkty współliniowe
względem długości promienia wodzącego
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # Xxxh 2012-05-28 21:01
Mi nie chodzi.. tzn skopiowałem kod, ale podałem inne zmienne, pierw takie jakie miałem w zadaniu i wyszło co innego niż oczekiwałem, potem ustawiłem trzy pierwsze od najniższej jak było tutaj opisane i też co innego wychodzi i na pewno nie zaznacza całości tylko tworzy coś trójkąto podobnego..
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Krzysztof T 2015-09-14 22:01
Wielkie dzięki dla Emila Hotkowskiego za jego kod. Bardzo się przydał.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz