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/


import "/sort" for Sort
import "/trait" for Comparable, Stepped
 
class Point is Comparable {
    construct new(x, y) {
        _x = x
        _y = y
    }
 
    x { _x }
    y { _y }
 
    compare(other) { (_x != other.x) ? (_x - other.x).sign : (_y - other.y).sign }
 
    toString { "(%(_x), %(_y))" }
}
 
/* ccw returns true if the three points make a counter-clockwise turn */
var ccw = Fn.new { |a, b, c| ((b.x - a.x) * (c.y - a.y)) > ((b.y - a.y) * (c.x - a.x)) }
 
var convexHull = Fn.new { |pts|
    if (pts.isEmpty) return []
    Sort.quick(pts)
    var h = []
 
    // lower hull
    for (pt in pts) {
        while (h.count >= 2 && !ccw.call(h[-2], h[-1], pt)) h.removeAt(-1)
        h.add(pt)
    }
 
    // upper hull
    var t = h.count + 1
    for (i in Stepped.descend(pts.count-2..0, 1)) {
        var pt = pts[i]
        while (h.count >= t && !ccw.call(h[-2], h[-1], pt)) h.removeAt(-1)
        h.add(pt)
    }
 
    h.removeAt(-1)
    return h
}
 
var pts = [
    Point.new(16,  3), Point.new(12, 17), Point.new( 0,  6), Point.new(-4, -6), Point.new(16,  6),
    Point.new(16, -7), Point.new(16, -3), Point.new(17, -4), Point.new( 5, 19), Point.new(19, -8),
    Point.new( 3, 16), Point.new(12, 13), Point.new( 3, -4), Point.new(17,  5), Point.new(-3, 15),
    Point.new(-3, -9), Point.new( 0, 11), Point.new(-9, -3), Point.new(-4, -2), Point.new(12, 10)
]
System.print("Convex Hull: %(convexHull.call(pts))")