成果物
今回のプログラムは予想の何倍も難しかったです。3日がかりです(最終的にさらにかかりました)。何とか、やり遂げました。
仕組み
ボロノイ図は、用意した点データをドロネー三角形分割で三角形に分割して、垂直二等分線を引いていくと出来上がります。一番の難所は、ドロネー三角形分割です。
今回非常に多く使う外接円の式はここを参考にしました。
ドロネー三角形分割
ドロネー三角形分割で参考にしたのはここのサイトです。
それでは、ドロネー三角形分割の流れについて説明していきたいと思います。まず、画面を覆い隠すサイズの三角形を作成します。（計算が楽になります）
ポイント（P）が追加されたとき以下実行↓
Pを含む△ABCを選択し、全三角形のリストから削除します（分割後に追加するため）
△ABCには下の図の処理を行います。探索中がなくなるまで、STEP2から下をループします。
初めての使ったこのサイトはGeoGebraという名前です。
処理が済んだら、完了済みを全三角形のリストに追加します。
これで、ドロネー三角形分割は完了です。（ただ、一つ一つのステップが難関です。）
ボロノイ図
三角形の垂直二等分線を引いていくと書かれていることが多いですが、
頂点の周りの三角形の外接円の中心をすべてつなげていくことで図形として取り出せるようにしています。
コード
今回はこちらのサイトをもとに再構成と改造をしています、再構成したものについては、フリーの配布の許可を頂きました。本当にありがとうございます。
原作のリポジトリです。
Voronoi_Baseは原作をボロノイ図に対応させたものです。
Voronoi_Simpleはシンプルなので、コードを理解したい人におすすめです。
Voronoi_Visualは、デザイン性や、操作性があります。ボロノイ図は表示が遅いです。
Voronoi_A_Starという、できた図形の最短ルートを求めるプログラムも作りました。
詳細はこちらをご覧ください。
私が改変したコードは、こちらのリポジトリにあります。
