%! (sort.inc) run /hulldict 32 dict def hulldict begin % u - v /vsub { 2 dict begin /v exch def /u exch def [ u 0 get v 0 get sub u 1 get v 1 get sub ] end } def % u - v rotated 90 degrees /vperp { 2 dict begin /v exch def /u exch def [ v 1 get u 1 get sub u 0 get v 0 get sub ] end } def /dot { 2 dict begin /v exch def /u exch def v 0 get u 0 get mul v 1 get u 1 get mul add end } def % P Q % tests whether P < Q in lexicographic order % i.e xP < xQ, or yP < yQ if xP = yP /comp { 2 dict begin /Q exch def /P exch def P 0 get Q 0 get lt P 0 get Q 0 get eq P 1 get Q 1 get lt and or end } def end % args: an arrya of points C % effect: returns the array of points on the boundary of % the convex hull of C, in clockwise order /hull { hulldict begin /C exch def /comp C quicksort /n C length def % Q might circle around to the start /Q n 1 add array def Q 0 C 0 get put Q 1 C 1 get put /i 2 def /k 2 def % i is next point in C to be looked at % k is next point in Q to be added % [ Q[0] Q[1] ... ] % scan the points to make the top hull n 2 sub { % P is the current point at right /P C i get def /i i 1 add def { % if k = 1 then just add P k 2 lt { exit } if % now k is 2 or more % look at Q[k-2] Q[k-1] P: a left turn (or in a line)? % yes if (P - Q[k-1])*(Q[k-1] - Q[k-2])^perp >= 0 P Q k 1 sub get vsub Q k 1 sub get Q k 2 sub get vperp dot 0 lt { % not a left turn exit } if /k k 1 sub def } loop Q k P put /k k 1 add def } repeat % done with top half % K is where the right hand point is /K k 1 sub def /i n 2 sub def Q k C i get put /i i 1 sub def /k k 1 add def n 2 sub { % P is the current point at right /P C i get def /i i 1 sub def { % in this pass k is always 2 or more k K 2 add lt { exit } if % look at Q[k-2] Q[k-1] P: a left turn (or in a line)? % yes if (P - Q[k-1])*(Q[k-1] - Q[k-2])^perp >= 0 P Q k 1 sub get vsub Q k 1 sub get Q k 2 sub get vperp dot 0 lt { % not a left turn exit } if /k k 1 sub def } loop Q k P put /k k 1 add def } repeat % strip Q down to [ Q[0] Q[1] ... Q[k-2] ] % excluding the doubled initial point [ 0 1 k 2 sub { Q exch get } for ] end } def