如何從Voronoï圖進行三角測量？

Question

我從一組點（用Boost.polygon）計算出一個Voronoï圖。

我嘗試找到一個Delaunay三角剖分，連接每個Voronoï邊緣的每個單元中心，但我錯過了一些邊緣。

在下圖中，紅點是我的初始點，藍線是沃羅諾伊邊緣（我忽略了無限邊緣），綠線是三角形邊緣（在每個藍色邊緣的綠色邊緣上，將兩個細胞起源）。

我們可以看到對角邊緣缺失。我錯過了什麼？

Answer 1

4個德洛奈頂點位於一個共同的圓圈，這是一個簡併情況。稍稍移動點，你會發現問題。