多角形の三角形分割

提供: MonoBook
ナビゲーションに移動 検索に移動

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

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

概要[編集 | ソースを編集]

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

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

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

主なアルゴリズム[編集 | ソースを編集]

点の三角形分割[編集 | ソースを編集]

多角形ではなく点の集合の三角形分割は以下のようなアルゴリズムがある。

関連項目[編集 | ソースを編集]