// Copyright (C) 2015 Dominic Charlesworth <dgc336@gmail.com>
// Author: Dominic Charlesworth <dgc336@gmail.com>
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 3
// of the License, or (at your option) any later version.
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <dgc336@gmail.com>.

function BowyerWatson(pointList) {
    var points = pointList.map(function (point) {
        return new Point(point.x, point.y);
    });
    var triangulation = new Triangulation(points);
    points.forEach(function (point) {
        BowyerWatsonInsert(point, triangulation);
    });
    return triangulation.edges();
}

function BowyerWatsonInsert(point, triangulation) {
    var badTriangles = [];
    triangulation.triangles.forEach(function (triangle) {
        if (triangle.contains(point).inCircumcircle()) {
            badTriangles.push(triangle);
        }
    });
    var polygon = [];
    badTriangles.forEach(function (triangle) {
        triangle.edges.forEach(function (edge) {
            if (badTriangles.every(function (t) {
                    return t === triangle ||
                        !t.contains(edge).inEdges();
                })) {
                polygon.push(edge);
            }
        });
    });
    badTriangles.forEach(function (triangle) {
        triangulation.remove(triangle);
    });
    polygon.forEach(function (edge) {
        triangulation.add(new Triangle(edge.vertices.concat(
            point)));
    });
}

function Triangulation(points) {
    this.superTriangle = this.getSuperTriangle(points);
    this.triangles = [this.superTriangle];
}
Triangulation.prototype.add = function (triangle) {
    this.triangles.push(triangle);
};
Triangulation.prototype.remove = function (triangle) {
    var index = this.triangles.indexOf(triangle);
    this.triangles.splice(index, 1);
};
Triangulation.prototype.getSuperTriangle = function (points) {
    var maxx = Math.max.apply(Math, points.map(function (point) {
        return point.x;
    }));
    var maxy = Math.max.apply(Math, points.map(function (point) {
        return point.y;
    }));
    return new Triangle([
        new Point(0, 0),
        new Point(maxx * 2, 0),
        new Point(0, maxy * 2)
    ]);
};
Triangulation.prototype.edges = function () {
    var edges = [];
    var superVertices = this.superTriangle.vertices;
    this.triangles.forEach(function (triangle) {
        triangle.edges.forEach(function (edge) {
            var element = {
                from: edge.vertex(0),
                to: edge.vertex(1)
            };
            if (!(~superVertices.indexOf(element.from) ||
                    ~superVertices.indexOf(element.to)
                )) {
                edges.push(element);
            }
        });
    });
    return edges;
};

function Triangle(vertices) {
    this.new = true;
    this.vertices = vertices;
    this.edges = [
        new Vector([this.vertices[0], this.vertices[1]]),
        new Vector([this.vertices[0], this.vertices[2]]),
        new Vector([this.vertices[1], this.vertices[2]])
    ];
    this.circumRadius = this.calculateCircumRadius();
    this.circumCenter = this.calculateCircumCenter();
}

Triangle.prototype.vertex = function (i) {
    return this.vertices[i];
};

// Calculation methods
Triangle.prototype.calculateCircumRadius = function () {
    var a = this.edges[0].length,
        b = this.edges[1].length,
        c = this.edges[2].length;
    var resultant = Math.sqrt((a + b + c) * (b + c - a) * (c + a - b) *
        (a + b - c)) || a / 2;
    return resultant ? (a * b * c) / resultant : a / 2;
};

Triangle.prototype.calculateCircumCenter = function () {
    var a = this.vertices[0],
        b = this.vertices[1],
        c = this.vertices[2];
    var D = 2 * ((a.x * (b.y - c.y)) + (b.x * (c.y - a.y)) + (c.x *
        (a.y - b.y)));
    var Ux = (((Math.pow(a.x, 2) + Math.pow(a.y, 2)) * (b.y - c.y)) +
            ((Math.pow(b.x, 2) + Math.pow(b.y, 2)) * (c.y - a.y)) +
            ((Math.pow(c.x, 2) + Math.pow(c.y, 2)) * (a.y - b.y))) /
        D,
        Uy = (((Math.pow(a.x, 2) + Math.pow(a.y, 2)) * (c.x - b.x)) +
            ((Math.pow(b.x, 2) + Math.pow(b.y, 2)) * (a.x - c.x)) +
            ((Math.pow(c.x, 2) + Math.pow(c.y, 2)) * (b.x - a.x))) /
        D;
    return new Point(Ux, Uy);
};

// Contains methods
Triangle.prototype.contains = function (thing) {
    this._contains = thing;
    return this;
};
Triangle.prototype.inCircumcircle = function () {
    return (new Vector([this.circumCenter, this._contains])).length <=
        this.circumRadius ? true : false;
};
Triangle.prototype.inEdges = function () {
    var edge = this._contains;
    return this.edges.some(function (e) {
        return edge.vertices[0] === e.vertices[0] &&
            edge.vertices[1] === e.vertices[1];
    });
};
Triangle.prototype.inTriangle = function () {
    var point = this._contains,
        B = this.vertex(1).minus(this.vertex(0)),
        C = this.vertex(2).minus(this.vertex(0)),
        P = point.minus(this.vertex(0)),
        d = (B.x * C.y) - (C.x * B.y);
    var weights = [
        ((P.x * (B.y - C.y)) + (P.y * (C.x - B.x)) + (B.x * C.y) -
            (C.x * B.y)) / d,
        ((P.x * C.y) - (P.y * C.x)) / d,
        ((P.y * B.x) - (P.x * B.y)) / d
    ];
    return weights.every(function (w) {
        return w >= 0 && w <= 1;
    });
};

function Vector(vertices) {
    this.vertices = vertices;
    this.length = this.calculateLength(vertices);
    this.midpoint = this.calculateMidpoint(vertices);
}
Vector.prototype.vertex = function (i) {
    return this.vertices[i];
};

Vector.prototype.calculateLength = function (v) {
    return Math.sqrt(Math.pow(Math.abs(v[0].x - v[1].x), 2) +
        Math.pow(Math.abs(v[0].y - v[1].y), 2));
};

Vector.prototype.calculateMidpoint = function (v) {
    return new Point((v[0].x + v[1].x) / 2, (v[0].y + v[1].y) / 2);
};
Vector.prototype.calculateGradient = function (v) {
    return (v[1].y - v[0].y) / (v[1].x - v[0].x);
};
Vector.prototype.minus = function (v) {
    return new Vector([
        new Point(this.vertex(0) - v.vertex(0).x, this.vertex(
            0).y - v.vertex(0).y),
        new Point(this.vertex(1) - v.vertex(1).x, this.vertex(
            1).y - v.vertex(1).y)
    ]);
};

function Point(x, y) {
    this.x = x;
    this.y = y;
}

Point.prototype.minus = function (p) {
    return new Point(this.x - p.x, this.y - p.y);
};