Find the points which form a convex hull from a set of arbitrary two dimensional points.

For example, given the points (16,3), (12,17), (0,6), (-4,-6), (16,6), (16,-7), (16,-3), (17,-4), (5,19), (19,-8), (3,16), (12,13), (3,-4), (17,5), (-3,15), (-3,-9), (0,11), (-9,-3), (-4,-2) and (12,10) the convex hull would be (-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19) and (-3,15).




See also
 Convex Hull (youtube)
 http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/


DEFINE POINTSIZE="4"
TYPE PointI=[INT x,y]
 
CARD FUNC GetAddr(INT ARRAY points BYTE index)
RETURN (points+POINTSIZE*index)
 
BYTE FUNC GetMinXIndex(INT ARRAY points BYTE pLen)
  PointI POINTER p
  BYTE i,index
  INT minX
 
  p=GetAddr(points,0)
  minX=p.x
  index=0
  FOR i=1 TO pLen-1
  DO
    p=GetAddr(points,i)
    IF p.x<minX THEN
      minX=p.x
      index=i
    FI
  OD  
RETURN (index)
 
BYTE FUNC Orientation(PointI POINTER p,q,r)
  INT v
  v=(q.y-p.y)*(r.x-q.x)
  v==-(q.x-p.x)*(r.y-q.y)
 
  IF v=0 THEN
    RETURN (0)
  ELSEIF v>0 THEN
    RETURN (1)
  FI
RETURN (2)
 
PROC ConvexHull(INT ARRAY points BYTE pLen
  INT ARRAY res BYTE POINTER resLen)
  PointI POINTER pSrc,pDst,p1,p2,p3
  BYTE minIndex,i,p,q
 
  IF pLen<3 THEN
    resLen^=pLen
    MoveBlock(res,points,pLen*POINTSIZE)
    RETURN
  FI
 
  resLen^=0
  minIndex=GetMinXIndex(points,pLen)
  p=minIndex q=0
  DO
    pSrc=GetAddr(points,p)
    pDst=GetAddr(res,resLen^)
    pDst.x=pSrc.x
    pDst.y=pSrc.y
    resLen^==+1
 
    q=(p+1) MOD pLen
    FOR i=0 TO pLen-1
    DO
      p1=GetAddr(points,p)
      p2=GetAddr(points,i)
      p3=GetAddr(points,q)
      IF Orientation(p1,p2,p3)=2 THEN
        q=i
      FI
    OD
    p=q
  UNTIL p=minIndex
  OD
RETURN
 
PROC PrintPoints(INT ARRAY points BYTE len)
  PointI POINTER p
  BYTE i
 
  FOR i=0 TO len-1
  DO
    p=GetAddr(points,i)
    PrintF("(%I,%I) ",p.x,p.y)
  OD
RETURN
 
PROC Main()
  INT ARRAY points=[
    16 3 12 17 0 6 65532 65530
    16 6 16 65529 17 65532 5 19
    19 65528 3 16 12 13 3 65532
    17 5 65533 15 65533 65527
    0 11 65527 65533 65532 65534
    12 10]
  INT ARRAY result(38)
  BYTE pLen=[19],rlen
 
  ConvexHull(points,pLen,result,@rlen)
 
  PrintE("Points:")
  PrintPoints(points,pLen)
  PutE() PutE()
  PrintE("Convex hull:")
  PrintPoints(result,rLen)
RETURN