Delaunay Triangle構造中不會移除的重複邊緣

Question

我正在嘗試實施Delaunay Triangulation。但是，我似乎有與邊緣創建重疊三角形的一個問題：

我立足我的實現作爲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

如果邊緣已經存在於邊緣緩衝區中，並且它不是超級三角形之後的第一個三角形，它需要從邊緣緩衝區中移除，而不是跳過循環。這個邊的頂點是新計算所需要的。只需將頂點重新插入其他緩衝區中，或從邊緣緩衝區中刪除邊緣。