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/


class Point(Number x, Number y) {
    method to_s {
        "(#{x}, #{y})"
    }
}
 
func ccw (Point a, Point b, Point c) {
    (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)
}
 
func tangent (Point a, Point b) {
    (b.x - a.x) / (b.y - a.y)
}
 
func graham_scan (*coords) {
 
    ## sort points by y, secondary sort on x
    var sp = coords.map { |a|
        Point(a...)
    }.sort { |a,b|
        (a.y <=> b.y) ||
        (a.x <=> b.x)
    }
 
    # need at least 3 points to make a hull
    if (sp.len < 3) {
        return sp
    }
 
    # first point on hull is minimum y point
    var h = [sp.shift]
 
    # re-sort the points by angle, secondary on x
    sp = sp.map_kv { |k,v|
        Pair(k, [tangent(h[0], v), v.x])
    }.sort { |a,b|
        (b.value[0] <=> a.value[0]) ||
        (a.value[1] <=> b.value[1])
    }.map { |a|
        sp[a.key]
    }
 
    # first point of re-sorted list is guaranteed to be on hull
    h << sp.shift
 
    # check through the remaining list making sure that
    # there is always a positive angle
    sp.each { |point|
        loop {
            if (ccw(h.last(2)..., point) >= 0) {
                h << point
                break
            } else {
                h.pop
            }
        }
    }
 
    return h
}
 
var hull = graham_scan(
    [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])
 
say("Convex Hull (#{hull.len} points): ", hull.join(" "))
 
hull = graham_scan(
    [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], [14,-9], [1,-9])
 
say("Convex Hull (#{hull.len} points): ", hull.join(" "))