javascript - 在我的 Bowyer-Watson 算法的实现中，是什么使它成为 O(n^2) 或更糟，而不是像它应该的那样 O(n log n)？

Question

我最近完成了用于在 Javascript 中计算平面中的 Delaunay 三角剖分的 Bowyer-Watson 算法。维基百科文章（维基百科沃森算法）说在特别退化的情况下它是 O(n log n) 到 O(n^2)。为什么我的实现总是超过 O(n^2)？是我的实现有问题，还是算法本身有问题？如果有帮助，我会在 onclick 事件和 Google Chrome 中运行该功能。

在检查从不同数量的节点计算所需的时间时，我注意到了这一点。100 个节点只需要大约 4 毫秒，然后 1'000 个节点需要 150 毫秒，然后一直到 10'000 个节点需要 60'000 毫秒。另一个奇怪的事情是，刷新选项卡后函数的前两次运行总是花费最长的时间。例如，对于 100 个节点，它需要 30ms -> 16ms -> 4ms -> 4ms -> ...。

相关代码来了。如果你懒得通读别人的草率代码（我不会怪你），请去上面的维基百科文章，看看你是否能在伪代码中找到问题所在。我已经非常密切地关注它，所以你在我的程序中发现的任何问题都可能来自这个算法的构造方式。祝你好运，并提前感谢。

// This is the function where the problem lies
function get_delaunay_triangulation(nodeList){
    var triangulation = []; // The list of triangles the function will output
    var badTriangles = []; // List of triangles no longer valid due to the insertion
    var nextNode; // Node inserted in each iteration
    var polygonHole = [];

    // The supertriangle has to contain all other nodes inside it
    /* Node is a class defined by its coords, and are accessed with node.x and node.y */
    var sTVertex1 = new Node(0, 0);
    // c.width and c.height are just the width and height of the screen
    var sTVertex2 = new Node(2 * c.width + 1, 0); 
    var sTVertex3 = new Node(0, 2 * c.height + 1);
    /* Edge is a class defined by its vertices, and are accessed with 
    edge.vertex1 and edge.vertex2 */
    var sTEdge1 = new Edge(sTVertex1, sTVertex2);
    var sTEdge2 = new Edge(sTVertex2, sTVertex3);
    var sTEdge3 = new Edge(sTVertex3, sTVertex1);
    /* Triangle is a class defined by its edges which you can access with triangle.edges, 
    but you can also access its vertices with triangle.vertices */
    var superTriangle = new Triangle([sTEdge1, sTEdge2, sTEdge3]);
    triangulation.push(superTriangle);

    for (var i = 0; i < nodeList.length; i++){
        nextNode = nodeList[i]; // The next point to be inserted

        badTriangles = []; // Resets badTriangles for every new point

        /* This loops through every triangle in the triangulation added so far. This 
        might be the cause of the slowdown, but I don't see why it would do that, and 
        why the wikipedia article wouldn't say anything about that. */
        for (var j = 0; j < triangulation.length; j++){
            var maybeBadTriangle = triangulation[j];
            var verticesInST = maybeBadTriangle.get_vertices_in(
            superTriangle.vertices);
            /* This checks every triangle in triangulation and adds the ones that
            are no longer valid due to the insertion. This part works well and is not
            likely to be the cause of the slowdown. */
            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);
            }
        }
        /* This part gathers the edges in badTriangles that are not shared by any other 
        triangle in badTriangles, so that polygonHole will contain the boundary of 
        the hole left behind when the bad triangles are removed. */
        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);
                }
            }
        }

        // Removes the triangles in badTriangles from triangulation
        for (var j = 0; j < badTriangles.length; j++){
            var index = triangulation.indexOf(badTriangles[j]);
            if (index != -1){
                triangulation.splice(index, 1);
            }
        }
        // Makes a new triangle from every edge of polygonHole to nextNode
        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)
                ])
            );
        }
    }
    /* When every point is inserted, the triangles which have a vertex in the original 
    superTriangle are removed from triangulation */
    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);
}

标签： javascriptperformancedelaunay

Answer 1

实现可以做成o(n.log(n))，但是维基百科给出的实现是o(n^2)。

请参阅为 delaunay 三角剖分实现 Bowyer-Watson 算法