8,231
回編集
差分
編集の要約なし
'''多角形の三角形分割'''（Polygon Triangulation）とは、１つの[[多角形]]（四角形以上）を「複数の[[三角形]]」に分割する[[アルゴリズム]]のことである。
== 概要 ==
== 主なアルゴリズム ==
* [[Ear Clipping]]
*: [[stackoverflow]]でおすすめ[[アルゴリズム]]を聞いたところ、[[Ear Clipper]]は理論上は最強だと思われるが、何も考えずに[[プログラミング言語]]に落とし込むと、[[浮動小数点]]の[[丸め誤差]]の蓄積などが原因で破綻し、この問題を回避する[[コード]]を入れると大して速くもないクソ実装になりがちだとされる。
* [[General Polygon Clipper]]
*: [[stackoverflow]]でおすすめされたアルゴリズム。
== 点の三角形分割 ==
多角形ではなく点の集合の三角形分割は以下のようなアルゴリズムがある。
* [[ドロネーの三角形分割]]（Delaunay Triangulation）
* [[最小重み三角形分割]]（Minimum Weight Triangulation）