在Delaunay三角形结构中没有删除重复边缘

问题描述

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

I'm trying to implement Delaunay Triangulation. However, I seem to be having a problem with edges creating overlapping triangles:

我的实现基于网站。我只是使用暴力循环来检查集合中是否存在边缘。

I'm basing my implementation as described on this site. I'm just using a brute force loop to check whether or not an edge already exists in the set.

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

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

I suspect that it's another part of my algorithm that's going wrong and causing this to happen, but I have implemented everything in a pretty straightforward manner. What is wrong with this code? Fiddle

推荐答案

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

If the edge already exist in the edge buffer and its not the first triangle after the super triangle it needs to be removed from the edge buffer and not to skip the loop. The vertices of this edge are needed for the new computation. Just reinsert the vertices in your other buffer or remove the edge from edge buffer.

这篇关于在Delaunay三角形结构中没有删除重复边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！