Delaunay Triangle 构造中未删除重复边

Question

我正在尝试实施 Delaunay 三角剖分。但是，我似乎遇到了边缘创建重叠三角形的问题：

我的实施基于 this 网站上的描述。我只是使用强力循环来检查集合中是否已经存在边。

v = vertex to be added
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
        remove triangle

我怀疑是我算法的另一部分出错导致了这种情况的发生，但我已经以非常简单的方式实现了所有内容。这段代码有什么问题？ Fiddle

Answer 1

如果边缘已经存在于边缘缓冲区中并且它不是超三角形之后的第一个三角形，则需要将其从边缘缓冲区中删除并且不要跳过循环。新计算需要这条边的顶点。只需将顶点重新插入其他缓冲区或从边缘缓冲区中删除边缘。

Delaunay Triangle 构造中未删除重复边

Duplicate edges not being removed in Delaunay Triangle construction

javascript

delaunay