Flip

flip.png

不要な辺を取り除いて、新しい辺を挿入すること。
ここでいう不要な辺とは、新しい辺を挿入した方がより均等な三角形になる場合、不要な辺という。

f.png

なぜデローニー三角形分割で辺のflipが必要なのか?

ちなみに辺のフリップを一切しないでデローニー三角形分割をするとこんなかんじになります。
no-flip.png
一番外側の三角形の頂点を取り除いたら、
とんがった三角形ばかりになり、図形がめちゃめちゃになります。下の図のように
no-flip-refine.png

なのでデローニー三角形分割のめんどくさいところではありますが、点のflipは必須の作業になります。

辺のflipでやること

  • 新しくできた三角形を、古い三角形ノードに2個子として追加する
  • 新しくできた三角形に基づいて隣接情報を更新する。

サポートサイト Wikidot.com