単純多角形

単純多角形：幾何学における基本図形

単純多角形とは、自身と交差することなく閉じた図形を形成する多角形です。直線で構成され、穴のない平面図形という特徴を持ちます。辺が交差する多角形は単純多角形ではありません。多くの場合、「単純」という修飾語は省略され、単に「多角形」と表現されます。

単純多角形の性質

単純多角形は以下の重要な性質を持ちます。

面積を持つ：常に面積を有し、その面積は計算可能です。
辺と頂点：辺（線分）は頂点（角）で接合し、頂点の数は辺の数と一致します。各頂点は2つの辺によって形成されます。
角度：辺が交わる角度は、通常180度ではありません。180度の場合は、それらの辺は1つの辺とみなされます。
位相的性質：数学的には、平面を内部と外部の2つの領域に分割します。位相幾何学的には、円と同値です。内部領域は円盤と同相です。

ジョーダン多角形

単純多角形は、ジョーダン多角形とも呼ばれます。これは、ジョーダン曲線定理によって、単純多角形が平面を内部と外部の2つの領域に分割することが保証されるためです。

弱単純多角形

弱単純多角形は、単純多角形とは異なる概念です。交差しない線分の集合が、位相的に円盤と等価な領域の境界を形成する場合、その境界は弱単純多角形と呼ばれます。コンピュータグラフィックスやCADでは、穴のある多角形を表現するために弱単純多角形が用いられることがあります。穴のある領域を表現するために、穴を外部境界に繋ぐ「カット」が作成され、弱単純多角形が形成されます。別の定義では、単純多角形の列の極限として弱単純多角形を定義することもできます。この定義では、辺が接することは許容されますが、交差は許されません。

計算幾何学における単純多角形

計算幾何学において、単純多角形は重要な役割を果たします。様々な計算タスクにおいて、入力として用いられます。

点の内外判定：与えられた点が単純多角形の内部にあるか外部にあるかを判定するアルゴリズムが存在します。
面積計算：単純多角形の面積を効率的に計算する式が知られています。
多角形分割：単純多角形を、正方形などの基本単位に分割する問題があります。最小個数の単位への分割や、辺の長さの合計が最小となる分割などが求められます。三角形分割も特殊なケースです。
ブール演算：単純多角形に対して、和集合、積集合、差集合などのブール演算を行うことができます。
凸包計算：単純多角形の凸包は効率的に計算できます。
ボロノイ図、中心軸、オフセット曲線、ミンコフスキー和：単純多角形に対して、これらの計算を行うことも可能です。

参考文献

Grünbaum, B.; Convex Polytopes, 2nd edition, Springer, 2003
計算幾何学に関する様々な論文や書籍
comp.graphics.algorithms FAQ
その他、関連する文献多数

単純多角形は、幾何学の基本的な概念であり、計算幾何学など、様々な分野で応用されています。その性質や計算上の扱いやすさから、多くのアルゴリズムの基礎として重要な役割を果たしています。

もう一度検索