class Triangle_Mesh{
    constructor(triangles){
        this.triangles = triangles;
        this.edges = this.get_edges();
        this.vertices = this.get_vertices();
    }

    get_edges(){
        var edges = [], tempEdge, edgesIncludesTempEdge;
        // Loop through all triangles
        for (var i = 0; i < this.triangles.length; i++){
            // Loopa igenom alla kanter i varje triangel
            for (var j = 0; j < 3; j++){
                tempEdge = this.triangles[i].edges[j];
                edgesIncludesTempEdge = false;
                for (var k = 0; k < edges.length; k++){
                    edgesIncludesTempEdge = edgesIncludesTempEdge
                    || edges[k].is_equal_to(tempEdge);
                }
                if (!edgesIncludesTempEdge){
                    edges.push(tempEdge);
                }
            }
        }
        return edges;
    }

    get_vertices(){
        var vertices = [];
        var tempVertex;
        // Loop through all triangles
        for (var i = 0; i < this.triangles.length; i++){
            // Loop through all vertices in all edges
            for (var j = 0; j < 3; j++){
                tempVertex = this.triangles[i].vertices[j];
                if (!vertices.includes(tempVertex)){
                    vertices.push(tempVertex);
                }
                if (!vertices.includes(tempVertex)){
                    vertices.push(tempVertex);
                }
            }
        }
        return vertices;
    }
}

class Polygon{
    constructor(edges){
        this.edges = edges;
        this.vertices = this.get_vertices();
    }

    get_vertices(){
        var vertices = [];
        // Loopa igenom alla kanter
        for (var i = 0; i < this.edges.length; i++){
            if (!vertices.includes(this.edges[i].vertex1)){
                        vertices.push(this.edges[i].vertex1);
            }
            if (!vertices.includes(this.edges[i].vertex2)){
                vertices.push(this.edges[i].vertex2);
            }
        }
        return vertices;
    }

    get_vertices_in(list){
        var returnList = [];
        for (var i = 0; i < list.length; i++){
            if (this.vertices.includes(list[i])){
                returnList.push(list[i]);
            }
        }
        return returnList;
    }
}

class Triangle extends Polygon{
    constructor(edges, vertices){
        super(edges, vertices);
        this.vertices = this.get_vertices();
        this.a = this.vertices[0];
        this.b = this.vertices[1];
        this.c = this.vertices[2];
        this.sortedClockwise = this.clockwise();
    }

    clockwise() {
        return (this.b.x - this.a.x)*(this.c.y - this.a.y) -
            (this.c.x - this.a.x)*(this.b.y - this.a.y) > 0;
    }

    circumcircle_contains(node) {
        var ax_ = this.a.x - node.x;
        var ay_ = this.a.y - node.y;
        var bx_ = this.b.x - node.x;
        var by_ = this.b.y - node.y;
        var cx_ = this.c.x - node.x;
        var cy_ = this.c.y - node.y;

        var determinant =
            (ax_*ax_ + ay_*ay_) * (bx_*cy_ - cx_*by_) -
            (bx_*bx_ + by_*by_) * (ax_*cy_ - cx_*ay_) +
            (cx_*cx_ + cy_*cy_) * (ax_*by_ - bx_*ay_);
        return (this.sortedClockwise) ?
            determinant > 0 : determinant < 0;
    }
}

class Edge{
    constructor(vertex1, vertex2){
        this.vertex1 = vertex1;
        this.vertex2 = vertex2;
    }

    is_equal_to(edge){
        var same = this.vertex1 == edge.vertex1 &&
        this.vertex2 == edge.vertex2;
        var sameButFlipped = this.vertex1 == edge.vertex2 &&
        this.vertex2 == edge.vertex1;
        return same || sameButFlipped;
    }

    get_length(){
        return dist(this.vertex1.x, this.vertex2.x,
                    this.vertex1.y, this.vertex2.y);
    }
}

class Node{
    constructor(x, y){
        this.x = x;
        this.y = y;
        this.relativeNeighbors = [];
        this.delaunayNeighbors = [];
        this.urquhartNeighbors = [];
    }

    isRightOfEdge(edge){
        var determinant =
        (edge.vertex2.x - edge.vertex1.x) * (this.y - edge.vertex1.y)
        - (edge.vertex2.y - edge.vertex1.y) * (this.x - edge.vertex1.x);
        return determinant > 0;
    }
}


// This is the function where the problem lies
function get_delaunay_triangulation(nodeList){
    var triangulation = [];
    var badTriangles = [];
    var nextNode;
    var polygonHole = [];

    var sTVertex1 = new Node(0, 0);
    var sTVertex2 = new Node(2 * c.width + 1, 0);
    var sTVertex3 = new Node(0, 2 * c.height + 1);
    var sTEdge1 = new Edge(sTVertex1, sTVertex2);
    var sTEdge2 = new Edge(sTVertex2, sTVertex3);
    var sTEdge3 = new Edge(sTVertex3, sTVertex1);
    var superTriangle = new Triangle([sTEdge1, sTEdge2, sTEdge3]);
    triangulation.push(superTriangle);

    for (var i = 0; i < nodeList.length; i++){
        nextNode = nodeList[i]; // Punkten som läggs till

        badTriangles = []; // Återställer badTriangles för varje ny punkt
        for (var j = 0; j < triangulation.length; j++){
            var maybeBadTriangle = triangulation[j];
            var verticesInST = maybeBadTriangle.get_vertices_in(
            superTriangle.vertices);
            if (verticesInST.length == 0){
                if (maybeBadTriangle.circumcircle_contains(nextNode)){
                    badTriangles.push(maybeBadTriangle);
                }
            } else if (verticesInST.length == 1) {
                var otherVertices = [...maybeBadTriangle.vertices];
                otherVertices.splice(
                    otherVertices.indexOf(verticesInST[0]), 1);
                var tempEdge = new Edge(otherVertices[0], otherVertices[1]);
                if (verticesInST[0].isRightOfEdge(tempEdge) ==
                nextNode.isRightOfEdge(tempEdge)){
                    badTriangles.push(maybeBadTriangle);
                }
            } else if (verticesInST.length == 2) {
                var otherVertices = [...maybeBadTriangle.vertices];
                var otherVertex;
                for (var k = 0; k < 3; k++){
                    if (!superTriangle.vertices.includes(otherVertices[k])){
                        otherVertex = otherVertices[k];
                        break;
                    }
                }
                var tempEdge = new Edge(otherVertex, new Node(
                otherVertex.x + verticesInST[1].x - verticesInST[0].x,
                otherVertex.y + verticesInST[1].y - verticesInST[0].y)
                );
                if (nextNode.isRightOfEdge(tempEdge) ==
                verticesInST[0].isRightOfEdge(tempEdge)){
                    badTriangles.push(maybeBadTriangle);
                }
            } else {
                badTriangles.push(maybeBadTriangle);
            }
        }

        polygonHole = [];
        for (var j = 0; j < badTriangles.length; j++){
            // Kollar varje kant i triangeln
            for (var k = 0; k < 3; k++){
                var testEdge = badTriangles[j].edges[k];
                var testEdgeIsUnique = true;
                for (var l = 0; l < badTriangles.length; l++){
                    for (var m = 0; m < 3; m++){
                        if (testEdge.is_equal_to(badTriangles[l].edges[m]) &&
                        l != j){
                            testEdgeIsUnique = false;
                            break;
                        }
                    }
                    if (!testEdgeIsUnique){ break; }
                }
                if (testEdgeIsUnique){
                    polygonHole.push(testEdge);
                }
            }
        }
        for (var j = 0; j < badTriangles.length; j++){
            var index = triangulation.indexOf(badTriangles[j]);
            if (index != -1){
                triangulation.splice(index, 1);
            }
        }
        var polygonEdge;
        for (var j = 0; j < polygonHole.length; j++){
            polygonEdge = polygonHole[j];
            triangulation.push(
                new Triangle([
                    polygonEdge,
                    new Edge(polygonEdge.vertex1, nextNode),
                    new Edge(polygonEdge.vertex2, nextNode)
                ])
            );
        }
    }
    var i = 0;
    while (i < triangulation.length){
        testVertices = triangulation[i].vertices;
        if (testVertices.includes(sTVertex1) ||
            testVertices.includes(sTVertex2) ||
            testVertices.includes(sTVertex3)){
            triangulation.splice(i, 1);
        } else {
            i++;
        }
    }

return new Triangle_Mesh(triangulation);