Delaunay Traversal

delaunay-traversal.png
step1.png 点Prが新しく加えたい点だとします。
Δ1の中にPrがあったので分割します
Δ1の子ノードに3つ追加されます。
Δ1の子ノードを調査します。(legalizeedgeします)
step2.png legalizeedgeした結果、他の点が、自分の三角形の外接円の中に入っていたら、flipが発生します。
flipが発生したら、親子関係を修正します。子が2つ発生します。
最終的に子を一個も持っていないリーフノードな三角形が、最終的に結果として出力する三角形になります

サポートサイト Wikidot.com