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
int ccw (struct point p0,
struct point p1,
struct point p2)
{
int dx1,dx2,dy1,dy2;
dx1 = p1.x - p0.x; dy1 = p1.y-p0.y;
dx2 = p2.x - p0.x; dy2 = p2.y-p0.y;
if (dx1*dy2 > dy1*dx2) return 1;
if (dx1*dy2 < dy1*dx2) return -1;
if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) return 1;
return 0;
}
Czy można użyć tej funkcji do porównywania podczas sortowania oraz sprawdzania warunku dla pętli
while z kroku 8 tzn czy porównywananie z użyciem tej funkcji będzie dawało poprawne wyniki
Załóżmy że uprzemy się na przechowywanie punktów w tablicy zamiast na liście
i zrezygnujemy z usuwania punktów współliniowych w kroku drugim algorytmu
Jak zmodyfikować pseudokod Cormena aby algorytm zatrzymywał się zwracając poprawny wynik
