耳刈り取り法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/11 07:56 UTC 版)
単調多角形を三角形分割する手法はtwo ears theoremに基づくものである。この定理は、4本以上の辺を持つ穴のない単純多角形は少なくとも2つの「耳（2辺が多角形の辺であり、残り1辺が多角形の内部に存在する三角形）」を持つという定理である。このアルゴリズムはこの「耳」を見つけ、その三角形を多角形から順に取り除くことで三角形分割を行う。 このアルゴリズムは実装が容易であるが他のアルゴリズムより遅く、穴を持たない多角形でしか動作しない。凸である頂点と凹である頂点を別のリストとして持つ実装の時間計算量はO(n2)である。この方法は耳刈り取り法もしくは耳取り除き法として知られるアルゴリズムで、Hossam ElGindy、Hazel Everett、Godfried Toussaintにより発見された。
※この「耳刈り取り法」の解説は、「多角形の三角形分割」の解説の一部です。
「耳刈り取り法」を含む「多角形の三角形分割」の記事については、「多角形の三角形分割」の概要を参照ください。
ウィキペディア小見出し辞書の「耳刈り取り法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 耳刈り取り法のページへのリンク
