「多角形の三角形分割」を編集中

'''多角形の三角形分割'''（Polygon Triangulation）とは、１つの[[多角形]]（四角形以上）を「複数の[[三角形]]」に分割する[[アルゴリズム]]のことである。

英語圏では単に「Triangulation」と呼ばれることが多いので、詳細を[[ググって]]調べたいときはこの単語を[[コピペ]]しろ。

== 概要 ==
[[コンピューター]]の世界で「[[ポリゴン]]（多角形）」という場合、[[2D]]ではそのまま「多角形」だが、[[3D]]では「複数の三角形」というのが一般的である。

たとえば[[Skia]]、[[CoreGraphics]]、[[WPF]]などで多角形を描画する場合は深く考える必要はない。
単に頂点座標を列挙（頂点座標の配列を用意）するだけでよい。

一方で、[[Vulkan]]、[[Metal]]、[[Direct3D]]で多角形を描画したいとなると、こいつらは基本的に「三角形の集合」しか受け付けないので事前に「複数の三角形」に分割してやる必要がある。この際に使われることが多いアルゴリズムである。

== 主なアルゴリズム ==
* [[Ear Clipping]]
*: [[stackoverflow]]でおすすめ[[アルゴリズム]]を聞いたところ、[[Ear Clipper]]は理論上は最強だと思われるが、何も考えずに[[プログラミング言語]]に落とし込むと、[[浮動小数点]]の[[丸め誤差]]の蓄積などが原因で破綻し、この問題を回避する[[コード]]を入れると大して速くもないクソ実装になりがちだとされる。
* [[General Polygon Clipper]]
*: [[stackoverflow]]でおすすめされたアルゴリズム。

== 点の三角形分割 ==
多角形ではなく点の集合の三角形分割は以下のようなアルゴリズムがある。
* [[ドロネーの三角形分割]]（Delaunay Triangulation）
* [[最小重み三角形分割]]（Minimum Weight Triangulation）

== 関連項目 ==
* [[三角形の秘密についてリークする]]
* [[ポリゴン]]
* [[テッセレーション]]
* [[Quadric Error Metrics]]

[[category: 算数]]