[Algorytmy] Algorytm Grahama, implementacja

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6701
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Pomógł: 1216 razy

[Algorytmy] Algorytm Grahama, implementacja

Post autor: mariuszm » 23 wrz 2017, o 23:20

Zordon, skoro implementowałeś Grahama kilka razy
to odpowiedz na kilka pytań

Kod: Zaznacz cały

    GRAHAM-SCAN(Q)
    1 let p0 be the point in Q with the minimum y-coordinate,
            or the leftmost such point in case of a tie
    2  let <p1,p2,...,pm> be the remaining points in Q,
              sorted by polar angle in counterclockwise order around p0
              (if more than one point has the same angle, remove all but
               the one that is farthest from p0)
    3  let S be an empty stack
    4  PUSH(p0,S)
    5  PUSH(p1,S)
    6  PUSH(p2,S)
    7  for i=3 to m
    8        while the angle formed by points NEXT-TO-TOP(S), TOP(S), and pi makes a nonleft turn
    9               POP(S)
    10      PUSH(pi,S)
    11 return S
Pomysł jest taki aby zrealizować ten algorytm na liście
Krok pierwszy zrealizowałbym w dwóch pętlach gdzie pierwsza znajduje punkt o najmniejszej
współrzędnej rzędnej a druga znajduje wśród punktów o najmniejszej rzędnej najmnieszą odciętą
Ciekawy jestem czy można zrealizować to w jednej pętli i jeśli tak to jak
Jeśli chodzi o krok drugi to wygląda na to że trzeba posortować punkty jednocześnie ze względu na
obydwie współrzędne biegunowe
(ze względu na argumenty zespolone rosnąco ze względu na moduły malejąco)
Chociaż jeśli chodzi o moduły to można się ograniczyć do znajdowania maximum

Dla listy widziałem procedurę sortującą przez scalanie ale tylko względem jednego klucza jednocześnie
Widziałem też procedurę usuwającą duplikaty z listy posortowanej co może być przydatne
Jak zrealizować warunek dla pętli while z kroku ósmego?
Czy tutaj przydatny będzie wyznacznik ?

Aby uniknąć arytmetyki zmiennoprzecinkowej można rozpatrywać kwadrat modułu
ale co z argumentem liczby zespolonej , jak go przechowywac ?

Czy program napisany na podstawie powyższego pseudokodu znalezionego u Cormena i reszty
będzie działał dla każdych danych wejściowych ?

Kod z książki Sedgewicka działał tylko dla niektórych danych wejściowych
Sprawdzałem tylko algorytm Jarvisa
Ostatnio zmieniony 24 wrz 2017, o 11:45 przez Afish, łącznie zmieniany 1 raz.
Powód: Nie podpinaj się pod cudze tematy.

Afish
Moderator
Moderator
Posty: 2816
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 353 razy

Re: [Algorytmy] Algorytm Grahama, implementacja

Post autor: Afish » 24 wrz 2017, o 11:50

Zazwyczaj chyba nie implementuje się Grahama bezpośrednio, tylko trochę go modyfikuje w celu uproszczenia. Stańczk na przykład sortuje po współrzędnych kartezjańskich i rozbija otoczkę na dwie części, a cały kod zajmuje ~10 linii.

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6701
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Pomógł: 1216 razy

Re: [Algorytmy] Algorytm Grahama, implementacja

Post autor: mariuszm » 30 wrz 2017, o 22:41

Czy jeżeli będziemy sortować po kartezjańskich to nadal będzie jeszcze algorytm Grahama ?
Gdybyśmy się uparli na tablicę to warto rozważyć rezygnację z usuwania współliniowych punktów
w kroku drugim
Krok drugi upraszcza się po poprawnym napisaniu funkcji porównującej

To jak zrealizować warunek dla pętli while jest nawet u Cormena
skąd wziąłem powyższy pseudokod tylko że kilka stron wcześniej

Tylko Cormen i reszta używają tam niepoprawnej wg mnie nazwy bo

Iloczyn wektorowy jest wektorem
Dotyczy wektorów w przestrzeni \(\displaystyle{ \mathbb{R}^3}\)
Czy aby na pewno długość tego wektora to \(\displaystyle{ \left| \vec{a\times b}\right|=\left| \vec{a}\right|\left| \vec{b}\right|\sin{\left( \angle\left( \vec{a},\vec{b}\right) \right) }}\)
bo gdyby liczyć długość z wektora z twierdzenia Pitagorasa
(pierwiastek z sumy kwadratów składowych) to zgubimy znak
O ten wzór na długość zapewne Cormenom chodzi

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6701
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Pomógł: 1216 razy

Re: [Algorytmy] Algorytm Grahama, implementacja

Post autor: mariuszm » 1 gru 2019, o 15:58

"Stańczk na przykład sortuje po współrzędnych kartezjańskich i rozbija otoczkę na dwie części, "
Tylko wtedy mamy inny algorytm
"a cały kod zajmuje ~10 linii."
Tak jak korzystamy z gotowców to można nawet w jednej linijce napisać
Po co wydzieliłeś temat Zordon chwalił się że kiedyś implementował algorytm Grahama więc chciałem aby
dokładniej opisał mi przynajmniej drugi punkt pseudokodu Cormena wtedy wiedziałbym że nie są to tylko przechwałki

Twoje wpisy niewiele wnoszą do tematu
Wygląda to na tzw nabijanie postów

ODPOWIEDZ