package;

typedef Point = { x:Float, y:Float };
typedef Line = { a:Point, b:Point };
typedef Vertex = { p:Point, diagonals:Array<Vertex> };

class Main {
    static function main() {
        // input =
        //
        //  o---o---o
        //      |'o'|
        //      o'-'o
        //
        var points = [ { x:0.0, y:0.0 },
                       { x:1.0, y:0.0 },
                       { x:1.0, y:1.0 },
                       { x:0.0, y:1.0 },
                       { x:0.5, y:0.5 },
                       { x:-1.0, y:0.0 }
        ];
        var lines = [ { a:points[0], b:points[1] },
                      { a:points[1], b:points[2] },
                      { a:points[2], b:points[3] },
                      { a:points[3], b:points[0] },
                      { a:points[0], b:points[4] },
                      { a:points[1], b:points[4] },
                      { a:points[2], b:points[4] },
                      { a:points[3], b:points[4] },
                      { a:points[0], b:points[5] }
        ];

        var exterior = exteriorPolygon(points, lines);
        // result =
        //
        //   o---#---o
        //       |   |
        //       o---o
        //
        // with the # vertex correctly duplicated.

        trace(Std.string(points));
        trace(Std.string(lines));
        trace(Std.string(exterior));
    }

    // return -1 if (a -> b -> c) is a left turn
    //         0 if (a -> b -> c) collinear
    //         1 if (a -> b -> c) is a right turn
    //
    // this presumes a y-axis pointing down for meanings
    // of left and right turn.
    static function orient(a:Point, b:Point, c:Point) {
        var ux = a.x - b.x;
        var uy = a.y - b.y;
        var vx = c.x - b.x;
        var vy = c.y - b.y;
        var perpdot = (ux * vy) - (uy * vx);
        return if (perpdot > 0) -1 else if (perpdot == 0) 0 else 1;
    }

    static function exteriorPolygon(points:Array<Point>, lines:Array<Line>) {
        // Transform points/lines to vertices.
        var vertices = [];
        for (p in points) {
            vertices.push({ p:p, diagonals: [] });
        }
        for (i in 0...points.length) {
            var p = points[i];
            var v = vertices[i];
            for (ab in lines) {
                function vertex(p:Point):Vertex {
                    for (j in 0...points.length) {
                        if (points[j] == p) return vertices[j];
                    }
                    return null;
                }
                if (ab.b == p) v.diagonals.push(vertex(ab.a));
                if (ab.a == p) v.diagonals.push(vertex(ab.b));
            }
        }

        // Find start point of exterior.
        var minimum = vertices[0];
        for (i in 1...vertices.length) {
            var v = vertices[i];

            if (v.p.x < minimum.p.x || (v.p.x == minimum.p.x && v.p.y < minimum.p.y)) {
                minimum = v;
            }
        }

        // Traverse exterior.
        var exterior = [];

        // Seed start-direction with a fake previous point.
        var current = minimum;
        var previous = { x:current.p.x - 1, y:current.p.y };
        do {
            exterior.push(current.p);

            // Find next point along exterior.
            var next = current.diagonals[0];
            var d1 = orient(previous, current.p, next.p);
            for (i in 1...current.diagonals.length) {
                var q = current.diagonals[i];
                var d2 = orient(previous, current.p, q.p);

                if (d1 * d2 == 1
                || (d1 * d2 == 0 && (d1 == 1 || d2 == 1))) {
                    if (orient(next.p, current.p, q.p) == 1) {
                        next = q;
                        d1 = d2;
                    }
                }
                else if (d1 == -1 || d2 == -1) {
                    if (d2 == -1) {
                        next = q;
                        d1 = d2;
                    }
                }
                else if (d1 == 0 && d2 == 0) {
                    var ax = current.p.x - previous.x;
                    var ay = current.p.y - previous.y;
                    var ux = next.p.x - current.p.x;
                    var uy = next.p.y - current.p.y;
                    var vx = q.p.x - current.p.x;
                    var vy = q.p.y - current.p.y;

                    var dot1 = (ax * ux) + (ay * uy);
                    var dot2 = (ax * vx) + (ay * vy);

                    if (dot1 < 0 && dot2 > 0) {
                        next = q;
                        d1 = d2;
                    }
                }
            }

            previous = current.p;
            current = next;
        }
        while (current != minimum);

        return exterior;
    }
}