単調多角形による三角形分割
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/11 07:56 UTC 版)
「多角形の三角形分割」の記事における「単調多角形による三角形分割」の解説
単純多角形の場合は以下のように単調多角形に分割できる。 各点について、隣り合う点が掃引線の同じ側にあるか、つまり「水平線や鉛直線を引いた場合に同じ側にあるかどうか」を確認する。もし同じ側にあれば掃引線を延長し、多角形と交差した点の辺の端点の内「違う側」の点間の線分で分割する。この処理を繰り返す。 （水平な）掃引線を下へと動かす場合に、両方の頂点が掃引線の上側にあり、下の図形が分割される場合がある。この場合、これから探索する図形が分割され、三角形分割のためにはそれぞれの図形に対して上記の処理を繰り返す必要がある。 このアルゴリズムを用いることで、単純多角形の三角形分割は O ( n log n ) {\displaystyle O(n\log n)} 時間で実行可能である。
※この「単調多角形による三角形分割」の解説は、「多角形の三角形分割」の解説の一部です。
「単調多角形による三角形分割」を含む「多角形の三角形分割」の記事については、「多角形の三角形分割」の概要を参照ください。
ウィキペディア小見出し辞書の「単調多角形による三角形分割」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 単調多角形による三角形分割のページへのリンク
