javascript - Delaunay 三 Angular 测量在网格的第三行失败

Question

我正在尝试使用简单的网格作为测试输入来实现 Delaunay 三 Angular 剖分，它似乎可以工作到第三行，然后三 Angular 形开始重叠。

第 1 行和第 2 行

第 3 行

决赛

我无法准确理解是什么导致了这种行为。这是一些伪代码:

for each vertex v
    edgeBuffer = [];
    for each triangle
        if v is in the triangle's circumscribed circle
            for each edge in the triangle
                check if it's already in edgeBuffer
                if not, add it
                otherwise, remove it
            remove triangle
    for each edge in edgeBuffer
        create a new triangle between edge and v

实际代码:

$("#add").click(function () { // User clicks a button to add the next vertex

    currVertIndex++;
    var v = vertList[currVertIndex];
    var edges = [];

    for (var i = 0; i < triangles.length; i++) {
        if (triangles[i].circc.containsVertex(v)) {
            var nextIndex;
            for (var e = 0; e < 3; e++) {
                nextIndex = (e + 1 == 3) ? 0 : e + 1;
                var newEdge = new Edge(triangles[i].v[e], triangles[i].v[nextIndex]);
                edges = addEdgeIfNew(newEdge, edges);
            }
            triangles.splice(i, 1);
            i--;
        }
    }

    for (var i = 0; i < edges.length; i++) {
        triangles.push(new Triangle(
            edges[i].v[0],
            edges[i].v[1],
            v
        ));
    }

});

这里出了什么问题？ Fiddle

编辑:这不是重复边缘未被删除的问题...这是我之前的问题。现在已经解决了。您可以将此处的图像与那里的图像进行比较来查看。

Answer 1

如果三 Angular 形重叠，则当前三 Angular 形的外 catch 中有 4 个顶点。然后你需要删除所有 4 个顶点。