8,452
回編集
差分
編集の要約なし
'''多角形の三角形分割'''（Polygon Triangulation）とは、１つの[[多角形]]（四角形以上）を「複数の[[三角形]]」に分割する[[アルゴリズム]]のことである。
英語圏では単に「Triangulation」と呼ばれることが多いので、詳細を[[ググって]]調べたいときはこの単語を[[コピペ]]しろ。
== 概要 ==
単に頂点座標を列挙（頂点座標の配列を用意）するだけでよい。
一方で、[[Vulkan]]、[[Metal]]、[[Direct3D]]で多角形を描画したいとなると、こいつらは基本的に「三角形の集合」しか受け付けないので事前に「複数の三角形」に分割してやる必要がある。このような用途で使われることが多い。で多角形を描画したいとなると、こいつらは基本的に「三角形の集合」しか受け付けないので事前に「複数の三角形」に分割してやる必要がある。この際に使われることが多いアルゴリズムである。他の用途はしらん。
== 主なアルゴリズム ==
* [[Ear Clipping]]
*: [[stackoverflow]]でおすすめ[[アルゴリズム]]を聞いたところ、[[Ear Clipper]]は理論上は最強だと思われるが、何も考えずに[[プログラミング言語]]に落とし込むと、[[浮動小数点]]の[[丸め誤差]]の蓄積などが原因で破綻し、この問題を回避する[[コード]]を入れると大して速くもないクソ実装になりがちだとされる。
* [[General Polygon Clipper]]
*: [[stackoverflow]]でおすすめされたアルゴリズム。
== 点の三角形分割 ==
多角形ではなく点の集合の三角形分割は以下のようなアルゴリズムがある。
* [[ドロネーの三角形分割]]（Delaunay Triangulation）
* [[最小重み三角形分割]]（Minimum Weight Triangulation）