delaunay - すべてのドロネー三角形をボロノイに接続するにはどうすればよいですか?

Question

エッジを共有するすべての三角形のリストがあります。ボロノイ図を描くにはどうすればよいですか？Delaunay 三角形をループして、頂点 1 = 頂点 2 および頂点 2 = 頂点 1 と比較します。同じエッジがある場合。また、頂点 1 = 頂点 1 および頂点 2 = 頂点 2 の場合もチェックします。方程式では、両側が異なる三角形です。Boywer watson アルゴリズムと同じループです。

Answer 1

Delaunay 三角形分割で 2 つの三角形が隣接する場合、これらの三角形の外心の間に線分を引きます。

Delaunay 三角形分割とボロノイ図の間の双対性には、覚えやすいルールがあります。双対要素の次元は、常に空間の次元になります。たとえば、2D では次のようになります。

ドロネー <-> ボロノイ

三角形 (2) + 点 (0) = 2

セグメント (1) + セグメント (1) = 2

ポイント (0) + セル (2) = 2

...3D でも同様です。