今日は、前回実装した Delaunay 分割のアルゴリズムをわかりやすく解説したいと思う。 まずは、前知識として 『詳解 OpenCV』 の記述をふたたび引用しよう。 外部三角形を作り、その頂点の 1 つを開始点とする(これにより、必ず外側の点から開始されることになる)。 内部の点を追加する。その後、すべての三角形の外接円を探索し、追加した点を含むような三角分割を削除する。 今削除した三角分割の外接円の内部にある、新しい点も含めて、グラフを三角分割し直す。 追加する点がなくなるまで、ステップ 2 に戻って繰り返す。 これをいかに解釈し、ソースコードに落とし込んでいくか。 計算幾何に興味がある方はもちろん、普段ネット上のソースをコピペして『動きさえすればそれでよい』と思っている方にも、この記事がプログラミングの楽しみを知るきっかけになれば幸いである(偉そうなこと言ってごめんなさいごめんなさい
![ProcessingでDelaunay分割(解説篇)](https://cdn-ak-scissors.b.st-hatena.com/image/square/421c334b2271ef610e1184840f931b94151989d4/height=288;version=1;width=512/http%3A%2F%2F3.bp.blogspot.com%2F-os6pHdi2jSs%2FTeiGkttINBI%2FAAAAAAAAASA%2F00qdgScfAZM%2Fw1200-h630-p-k-no-nu%2F20110603001.png)