単純多角形
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/11 08:25 UTC 版)
 | この項目「単純多角形」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en:Simple polygon） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2023年3月） |
 |
 | この記事の文章は日本語として不自然な表現、または文意がつかみづらい状態になっています。 |
 | この記事は別の言語から大ざっぱに翻訳されたものであり、場合によっては不慣れな翻訳者や機械翻訳によって翻訳されたものかもしれません。 |
単純多角形（たんじゅんたかくけい、英: Simple_polygon）は、幾何学にて、それ自身と交差せず、穴のない多角形。
直線で交差しない線分または「辺」がペアで結合されて 1 つの閉じたパスを形成するフラットな形状のものをいう。
解説
辺が交差する場合、多角形は単純ではない。「単純」という修飾語は省略されることが多く、上記の定義は一般に多角形を定義するものと理解される。
上記の定義により、以下が保証される。
- 多角形は、常に測定可能な領域を持つ領域（面積と呼ばれる）を囲む[訳語疑問点]。
- 多角形を構成する線分 (辺または辺と呼ばれる) は、頂点 (単数形: 頂点) またはあまり形式的ではない「角」と呼ばれる端点でのみ交わる。
- 正確には2つの角が各頂点で交わる。
- 角の数は常に頂点の数と同じである。
辺で交わる 2 つの端は、通常、直線 (180°) ではない角度を形成する必要がある。それ以外の場合、同一線上の線分は 1 つの側面の一部と見なされる。
数学者は通常、「多角形」を使用して、囲まれた領域ではなく、線分によって構成される形状のみを参照するが、「多角形」を使用して、有限シーケンスで構成される閉じたパスによって境界付けられた平面図を参照する場合がありる 。直線セグメントの（つまり、閉じた多角形チェーンによる）。使用中の定義によれば、この境界は幾何学自体の一部を形成する場合と形成しない場合がある[1]。
単純な多角形はジョーダン多角形とも呼ばれる。ジョルダン曲線定理を使用して、このような多角形が平面を内側の領域と外側の領域の 2 つの領域に分割することを証明できるからである。平面内の多角形は、位相的に円と等価である場合にのみ単純である。その内部は位相的に円盤に相当する。
弱単純多角形
交差しない線分の集まりが、トポロジー的に円盤と等価な平面の領域の境界を形成する場合、この境界は弱単純多角形と呼ばれる。[2]左の画像では、ABCDEFGHJKLM は、この定義による弱単純多角形であり、青色が境界となる領域を示している。このタイプの弱単純多角形は、コンピューター グラフィックスやCADで発生する可能性がある[訳語疑問点]。穴のある多角形領域のコンピューター表現として: 各穴に対して「カット」が作成され、それを外部境界に接続する。上の画像を参照すると、ABCM は穴 FGHJ のある平面領域の外部境界である。カットされた ED は、穴と外部を接続し、2 回トラバースされ[訳語疑問点]、結果として得られる弱く単純な幾何学表現になる。
弱く単純な多角形の別のより一般的な定義では、フレシェ距離の下で収束する、同じ組み合わせタイプの単純な多角形のシーケンスの限界である。これは、そのような多角形はセグメントが接触することはできるが、交差することはできないという概念を定式化したものである。ただし、このタイプの弱く単純な幾何学は、領域の境界を形成する必要はありません。その「内部」は空である可能性があるからである。たとえば、上の画像を参照すると、この定義によれば、多角形チェーン ABCBA は弱単純多角形である。これは、多角形 ABCFGHA の「絞り込み」の限界と見なすことができる。
計算問題
計算幾何学では、いくつかの重要な計算タスクに単純な多角形の形式の入力が含まれる。これらの問題のそれぞれにおいて、内部と外部の区別は、問題の定義において重要である。
- 多角形の点：幾何学テストでは、単純な幾何学Pとクエリ ポイントqについて、q がPの内部にあるかどうかを判断する。
- 多角形の面積を計算するための簡単な式が知られている。つまり、多角形の内部の面積である。
- 幾何学 パーティションは、基本単位 (正方形など) のセットであり、重複せず、和集合が幾何学に等しくなりる。多角形分割問題は、ある意味で最小の分割を見つける問題である。たとえば、ユニットの数が最小の分割、または辺の長さの合計が最小の分割である。
- 幾何学 パーティションの特殊なケースは、幾何学の三角形分割である。単純な幾何学を三角形に分割する。凸多角形は簡単に三角形化できるが、一般的な単純な多角形を三角形化するのは、多角形の外側に交差するエッジを追加することを避ける必要があるため、より困難である。それにもかかわらず、バーナード・チャゼルは1991年に、n個の頂点を持つ単純な多角形は
- 幾何学 パーティションの特殊なケースは、幾何学の三角形分割である。単純な幾何学を三角形に分割する。凸多角形は簡単に三角形化できるが、一般的な単純な多角形を三角形化するのは、多角形の外側に交差するエッジを追加することを避ける必要があるため、より困難である。それにもかかわらず、バーナード・チャゼルは1991年に、n個の頂点を持つ単純な多角形は
単純多角形
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/23 18:21 UTC 版)
単純多角形（自己交差を持たない多角形）の凸包は、その多角形によって複数の多角形に分割されている。そのうちの1つは多角形自体であり、残りは多角形境界の断片と凸包の一辺で囲まれたポケットである。単純多角形の凸包を構築する問題について多くのアルゴリズムが公開されていたが、それらのほぼ半分は正しくなかった。マッカラムとエイビスは最初の正しいアルゴリズムを提供した。 グラハム & ヤオ (1983)、あるいはリー (1983) による簡略版では、単一のスタックデータ構造のみを使用する。彼らのアルゴリズムは、多角形の左端の頂点から時計回りにたどる。その際、まだポケットの中に位置すると判明してない頂点を格納していき、スタック上に凸多角形状の点のリストを作る。この各ステップでは、スタックのトップの点から、それと隣接するポケットではない頂点まで、多角形にそった経路をたどる。そしてこの新しい頂点とスタックの上から2つの頂点が凸状の形にならない場合、スタックのポップをしてから、最後に新しい頂点を追加する。時計回りの処理が開始点に達すると、このスタック内の頂点列が凸包となる。
※この「単純多角形」の解説は、「凸包アルゴリズム」の解説の一部です。
「単純多角形」を含む「凸包アルゴリズム」の記事については、「凸包アルゴリズム」の概要を参照ください。
- 単純多角形のページへのリンク
