[Algorytmy] Algorytm Grahama, implementacja

[Mariusz M]

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

[Afish]

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.

[Mariusz M]

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

[Mariusz M]

"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

[Mariusz M]

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.

Tak jak podejrzewałem gdy wprowadzimy powyższe zmiany to już nie będzie to algorytm Grahama
No fajnie jeżeli skorzystamy z gotowców to może i cały kod zajmie ~10 linii

Algorytm po wprowadzeniu tych zmian można znaleźć choćby na wikipedii
Po wprowadzeniu licznika węzłów jakoś udało mi się go przepisać z użyciem listy
Użycie licznika wiążę się jednak z pewnymi ograniczeniami
np gdy liczba węzłów przekroczy zakres typu integer

Na wikipedii algorytm z wprowadzonymi zmianami nazywają Andrew's monotone chain