ProcessingでDelaunay分割（実装篇）
前々回のあらすじ： 砕け散るエフェクトを作った。 ……それはよいのだが、いかんせんやっつけ仕事だったため、砕け散る破片の形状生成がびっくりするほど適当だった。 もうちょっとうまく破片を作るために、今回は計算幾何のアルゴリズムの中でも比較的有名な Delaunay 分割に挑戦してみた。 まずはじめに、結果から示そう。 Delaunay 分割は、ランダムに与えられた点を結び、下のような無数の三角形を作る手法である。 さて。 Delaunay 三角分割法に関しては、Gary Bradski, Adrian Kaehler 著、松田 晃一 訳『詳解 OpenCV』にこんな解説がある。 Delaunay 三角分割法は、空間内の点を連結して三角形のグループにし、その三角形のすべての角に対する最小角度が最大になるようにするテクニックで、1934年に発明されました。 （中略） 与えられた任意の三角形の頂点
ProcessingでDelaunay分割（解説篇）
今日は、前回実装した Delaunay 分割のアルゴリズムをわかりやすく解説したいと思う。 まずは、前知識として 『詳解 OpenCV』 の記述をふたたび引用しよう。 外部三角形を作り、その頂点の 1 つを開始点とする（これにより、必ず外側の点から開始されることになる）。 内部の点を追加する。その後、すべての三角形の外接円を探索し、追加した点を含むような三角分割を削除する。 今削除した三角分割の外接円の内部にある、新しい点も含めて、グラフを三角分割し直す。 追加する点がなくなるまで、ステップ 2 に戻って繰り返す。 これをいかに解釈し、ソースコードに落とし込んでいくか。 計算幾何に興味がある方はもちろん、普段ネット上のソースをコピペして『動きさえすればそれでよい』と思っている方にも、この記事がプログラミングの楽しみを知るきっかけになれば幸いである（偉そうなこと言ってごめんなさいごめんなさい
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
