扇形三角測量

計算幾何学において、扇形三角形分割は、頂点を選択し、多角形の他のすべての頂点に辺を描くことによって多角形を三角形分割する簡単な方法です。すべての多角形をこの方法で三角形分割できるわけではないため、この方法は通常、凸多角形にのみ使用されます。^{[ 1 ]}

すべての三角形分割に共通する特性に加えて、扇形三角形分割には以下の特性があります。

• すべての凸多角形は扇形三角形分割が可能であるが、すべての多角形が可能であるわけではない。
• 凹面頂点が1つしかない多角形は、対角線がその凹面頂点から引かれている限り、常に扇形三角形分割が可能である。
• 多角形が扇形三角形分割可能かどうかは、美術館問題を解くことで知ることができます。つまり、多角形内のすべての点から見える頂点が少なくとも1つ存在するかどうかを判定します。
• 多角形の三角形分割${\displaystyle n}$頂点の使用${\displaystyle n-3}$対角線を生成し、${\displaystyle n-2}$三角形。^{[ 2 ]}
• 頂点の順序付きリストが利用可能であれば、三角形のリストを生成するのは簡単で、線形時間で計算できます。そのため、三角形のリストを明示的に保存する必要はなく、したがって、多くのグラフィックライブラリは、この三角形分割に基づいて多角形を表現するプリミティブを実装しています。^{[ 3 ]}
• この三角分割は、ラスタライズや衝突検出などの特定の問題を解決するのに適していますが、原点となる頂点に多数の近傍点が蓄積され、三角分割の内部角度が不均一に分布するため、他のタスクには適さない場合があります。

• 三角形のファン