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/


--
-- demo/rosetta/Convex_hull.exw
-- ============================
--
with javascript_semantics
constant tests = {{{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}, {12, 10}},
                  {{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}, {12, 10}, {1,-9}, {1,-9}},
                  {{0,0}, {5,5}, {5,0}, {0,5}},
                  {{0,0}, {0,1}, {0,2},
                   {1,0}, {1,1}, {1,2},
                   {2,0}, {2,1}, {2,2}},
                  {{-8,-8}, {-8,4}, {-8,16},
                   { 4,-8}, { 4,4}, { 4,16},
                   {16,-8}, {16,4}, {16,16}}}

integer t = 1 -- idx to tests, for the GTITLE.

enum x, y
function ccw(sequence a, b, c)
    return (b[x] - a[x]) * (c[y] - a[y])
         > (b[y] - a[y]) * (c[x] - a[x])
end function
 
function convex_hull(sequence points)
    sequence h = {}
    points = sort(deep_copy(points))
 
    /* lower hull */
    for i=1 to length(points) do
        while length(h)>=2
          and not ccw(h[$-1], h[$], points[i]) do
            h = h[1..$-1]
        end while
        h = append(h, points[i])
    end for
 
    /* upper hull */
    integer t = length(h)+1
    for i=length(points) to 1 by -1 do
        while length(h)>=t
          and not ccw(h[$-1],h[$],points[i]) do
            h = h[1..$-1]
        end while
        h = append(h, points[i])
    end for
 
    h = h[1..$-1]
    return h
end function

for i=1 to length(tests) do
    printf(1,"For test set: ")
    pp(tests[i],{pp_Indent,13,pp_Maxlen,111})
    printf(1,"Convex Hull is: ")
    pp(convex_hull(tests[i]))
end for

-- plots the test points in red crosses and the convex hull in green circles
include pGUI.e
include IupGraph.e
Ihandle dlg, graph

function get_data(Ihandle /*graph*/)
    IupSetStrAttribute(graph, "GTITLE", "Marks Mode (%d/%d)", {t, length(tests)})
    sequence tt = tests[t],
          {x,y} = columnize(tt),
        {cx,cy} = columnize(convex_hull(tt))
    -- and close the loop:
    cx &= cx[1]
    cy &= cy[1]
    return {{x,y,CD_RED},
            {cx,cy,CD_GREEN,"HOLLOW_CIRCLE","MARKLINE"}}
end function

function key_cb(Ihandle /*ih*/, atom c)
    if c=K_ESC then return IUP_CLOSE end if -- (standard practice for me)
    if c=K_F5 then return IUP_DEFAULT end if -- (let browser reload work)
    if c=K_LEFT then t = iff(t=1?length(tests):t-1) end if
    if c=K_RIGHT then t = iff(t=length(tests)?1:t+1) end if
    IupUpdate(graph)
    return IUP_CONTINUE
end function

IupOpen()
graph = IupGraph(get_data,"RASTERSIZE=640x480,MODE=MARK")
dlg = IupDialog(graph,`TITLE="Convex Hull",MINSIZE=270x430`)
IupSetAttributes(graph,"XTICK=2,XMIN=-12,XMAX=20,XMARGIN=25,YTICK=2,YMIN=-12,YMAX=20")
IupSetInt(graph,"GRIDCOLOR",CD_LIGHT_GREY)
IupShow(dlg)
IupSetCallback(dlg, "K_ANY", Icallback("key_cb"))
IupSetAttribute(graph,`RASTERSIZE`,NULL)
if platform()!=JS then
    IupMainLoop()
    IupClose()
end if
