成果物
基本的なDelaunay図の最終形態とも言うべきConstrained Delaunayがとうとう完成しました!これを使うと、自由自在に穴をあけたり、線を入れたりすることができます。仕組み自体はシンプルですが、接続情報の変更が非常に複雑で、難しかったです。改良しようとやってみましたが、失敗したので、そのままのコードを翻訳しています。文字でこれを行ったり、複数の図形で行うととても綺麗なものが出来上がりそうなので、これからやっていきます!
仕組み
Delaunay生成
Constraint(必ず通っていなければならない線)を指定します。そして、Delaunay図の頂点にConstraintを追加して、図を生成します。※この状態では通らなければならない点を通っていません。
制約の追加
Constraintと交差している線を探し出し、交差がなくなるまで、Flip(面の張り直し)をします。張り直したあとは、きちんとしたDelaunay図になるよう調整します。
面の削除(任意)
三角形を伝うようにしてConstraintの中の三角形を削除しています。Constraintは時計回りだという想定のもと作られていますが、反時計回りにするとConstraintの外が削除されるようになります。
参考
Constrained Delaunayはこちらのコードをもとにしています。
github.com
元のDelaunay図作成はHull Voronoi 3Dを利用しています。(Flipなど他のアルゴリズムでも可能です)
nekodigi.hatenablog.com
コード
Constrained Delaunay 2という名前で追加しています。
github.com
エラーが多いですが、改良に成功すれば非常に便利になるConstrained Delaunay Testというものも追加しています。改良に成功したという方は報告お願いします。