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 std.algorithm.sorting;
import std.stdio;
 
struct Point {
    int x;
    int y;
 
    int opCmp(Point rhs) {
        if (x < rhs.x) return -1;
        if (rhs.x < x) return 1;
        return 0;
    }
 
    void toString(scope void delegate(const(char)[]) sink) const {
        import std.format;
        sink("(");
        formattedWrite(sink, "%d", x);
        sink(",");
        formattedWrite(sink, "%d", y);
        sink(")");
    }
}
 
Point[] convexHull(Point[] p) {
    if (p.length == 0) return [];
    p.sort;
    Point[] h;
 
    // lower hull
    foreach (pt; p) {
        while (h.length >= 2 && !ccw(h[$-2], h[$-1], pt)) {
            h.length--;
        }
        h ~= pt;
    }
 
    // upper hull
    auto t = h.length + 1;
    foreach_reverse (i; 0..(p.length - 1)) {
        auto pt = p[i];
        while (h.length >= t && !ccw(h[$-2], h[$-1], pt)) {
            h.length--;
        }
        h ~= pt;
    }
 
    h.length--;
    return h;
}
 
/* ccw returns true if the three points make a counter-clockwise turn */
auto ccw(Point a, Point b, Point c) {
    return ((b.x - a.x) * (c.y - a.y)) > ((b.y - a.y) * (c.x - a.x));
}
 
void main() {
    auto points = [
        Point(16,  3), Point(12, 17), Point( 0,  6), Point(-4, -6), Point(16,  6),
        Point(16, -7), Point(16, -3), Point(17, -4), Point( 5, 19), Point(19, -8),
        Point( 3, 16), Point(12, 13), Point( 3, -4), Point(17,  5), Point(-3, 15),
        Point(-3, -9), Point( 0, 11), Point(-9, -3), Point(-4, -2), Point(12, 10)
    ];
    auto hull = convexHull(points);
    writeln("Convex Hull: ", hull);
}