多角形の三角形分割

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

概要

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

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

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