「多角形の三角形分割」の版間の差分
ナビゲーションに移動
検索に移動
Administrator (トーク | 投稿記録) |
Administrator (トーク | 投稿記録) |
||
| 12行目: | 12行目: | ||
== 主なアルゴリズム == | == 主なアルゴリズム == | ||
| + | * [[Ear Clipping]] | ||
| + | *: [[stackoverflow]]でおすすめ[[アルゴリズム]]を聞いたところ、[[Ear Clipper]]は理論上は最強だと思われるが、何も考えずに[[プログラミング言語]]に落とし込むと、[[浮動小数点]]の[[丸め誤差]]の蓄積などが原因で破綻し、この問題を回避する[[コード]]を入れると大して速くもないクソ実装になりがちだとされる。 | ||
| + | * [[General Polygon Clipper]] | ||
| + | *: [[stackoverflow]]でおすすめされたアルゴリズム。 | ||
| + | |||
| + | == 点の三角形分割 == | ||
| + | 多角形ではなく点の集合の三角形分割は以下のようなアルゴリズムがある。 | ||
* [[ドロネーの三角形分割]]（Delaunay Triangulation） | * [[ドロネーの三角形分割]]（Delaunay Triangulation） | ||
* [[最小重み三角形分割]]（Minimum Weight Triangulation） | * [[最小重み三角形分割]]（Minimum Weight Triangulation） | ||
2022年9月16日 (金) 01:25時点における最新版
多角形の三角形分割（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）
