多角形チェーン

幾何学において、多角形連鎖^[a]は、連結された一連の線分です。より正式には、多角形連鎖は、${\displaystyle P}$頂点と呼ばれる一連の点によって指定される曲線です。曲線自体は、連続する頂点を連結する線分で構成されます。 ${\displaystyle (A_{1},A_{2},\dots ,A_{n})}$

単純な多角形チェーンとは、連続するセグメントのみがその端点でのみ交差するチェーンです。

閉じた多角形連鎖とは、最初の頂点が最後の頂点と一致するか、または最初の頂点と最後の頂点が線分によっても接続される連鎖である。^[1]平面 上の単純な閉じた多角形連鎖は、単純な多角形の境界である。多くの場合、「多角形」という用語は「閉じた多角形連鎖」の意味で使用されますが、多角形領域と多角形連鎖を区別することが重要な場合もあります。空間的に閉じた多角形連鎖は、斜め「多角形」とも呼ばれます。

直線Lが存在し、Lに垂直なすべての線が最大で 1 回しか交差しない場合、多角形連鎖は単調と呼ばれます。すべての非自明な単調多角形連鎖は開いています。比較すると、単調多角形は、正確に 2 つの単調連鎖に分割できる多角形 (閉じた連鎖) です。^[2]区分線形関数のグラフは、水平線に関して単調連鎖を形成します。

ポリゴン チェーンの各セグメントは、通常、連続する頂点間の線形補間を使用して線形にパラメータ化されます。チェーン全体については、実際のアプリケーションでは 2 つのパラメータ化が一般的です。チェーンの各セグメントには、最初の頂点のインデックスに対応するパラメータの単位間隔を割り当てることができます。または、チェーンの各セグメントには、セグメントの長さに対応するパラメータの間隔を割り当てることができます。これにより、パラメータはチェーン全体に沿って円弧の長さに均一に対応します。

少なくとも 個の点からなるすべての集合には、すべての傾きが同じ符号を持つ少なくとも 個の辺からなる多角形のパスが含まれます。これはエルデシュ・シェケレスの定理の系です。 ${\displaystyle n}$${\displaystyle \lfloor {\sqrt {n-1}}\rfloor }$

多角形連鎖は、より複雑な曲線を近似するためによく使用されます。この文脈では、Ramer-Douglas-Peuckerアルゴリズムを使用して、正確な近似として機能するセグメントの少ない多角形連鎖を見つけることができます。^{[3] [4]}

グラフ描画では、エッジを直線セグメントとして描画すると交差、エッジと頂点の衝突、またはその他の望ましくない特徴が生じる描画スタイルにおいて、グラフのエッジを表すために多角形チェーンがよく使用されます。この文脈では、描画の視覚的な乱雑さを減らすために、できるだけ少ないセグメントと曲げでエッジを描画することが望まれることがよくあります。曲げの数を最小限に抑える問題は、曲げの最小化と呼ばれます。^[5]

コンピュータ支援による幾何設計では、滑らかな曲線は多くの場合、制御点のリストによって定義されます(例:ベジェ曲線セグメントの定義)。制御点が相互に接続されると、制御ポリゴンと呼ばれる多角形のチェーンが形成されます。

多角形連鎖は計算幾何学における基本的なデータ型でもある。例えば、リーとプレパラタの点配置アルゴリズムは、任意の平面細分を単調な連鎖の順序付けられたシーケンスに分解することによって動作し、点配置クエリ問題はバイナリ検索によって解決される。この方法は後に改良され、点配置問題に最適な時間制限を与えるようになった。^[6]

地理情報システムでは、ラインストリングは任意の線形ジオメトリを表すことができ、よく知られたテキストマークアップを使用してLineStringまたはとして記述することができますMultiLineString。^[7]線形リング（またはLinearRing）は、ポリゴンジオメトリを構築するために使用される閉じた単純なポリゴンチェーンです。

• 連鎖（代数的位相幾何学）、1次元の場合に多角形連鎖を含む単体の形式的な組み合わせ
• 複合ベジェ曲線。多角形チェーンの各直線を滑らかな曲線に置き換える一般化です。
• リンク距離、ポリゴン内の2点を結ぶ最短チェーンのセグメント数
• 区分回帰
• パス（グラフ理論）、抽象グラフにおける類似概念
• 多面体地形、単調な多角形チェーンの 3D 一般化
• スパイラングル、螺旋状の多角形の鎖
• 棒数、結び目を閉じた多角形の鎖として表すことに基づく結び目不変量
• トラバース、測量への応用