ストレートスケルトン

幾何学において、直線スケルトンは位相スケルトンによって多角形を表現する方法である。これは中軸といくつかの点で似ているが、スケルトンが直線セグメントで構成されているのに対し、多角形の中軸は放物線を含む場合がある点で異なる。しかし、どちらも基礎となる多角形とホモトピー同値である。^[1]

直線スケルトンは、Aichholzerら(1995) ^[2]によって単純な多角形に対して最初に定義され、AichholzerとAurenhammer(1996)によって平面直線グラフ(PSLG)に一般化されました。 ^[3] 屋根面の投影としての解釈については、GA Peschka(1877)によってすでに広範囲に議論されています。^[4]

多角形の直線骨格は、多角形のエッジが一定の速度で内側に平行に移動する、連続的な縮小プロセスによって定義されます。エッジがこのように移動すると、エッジのペアが交わる頂点も、頂点の角度に応じた速度で移動します。移動する頂点の 1 つが隣接していないエッジと衝突すると、衝突によって多角形が 2 つに分割され、各部分でプロセスが続行されます。直線骨格は、このプロセスで移動する頂点によって描かれる曲線のセットです。図では、上の図は縮小プロセスを示し、中央の図は直線骨格を青で表しています。

直線スケルトンは、それが定義される縮小プロセスをシミュレートすることによって計算できます。直線スケルトンを計算するためのさまざまなアルゴリズムが提案されていますが、入力に対する仮定や、入力ポリゴンが縮小するときに組み合わせの変化を検出するために使用する データ構造が異なります。

以下のアルゴリズムは、多角形、穴のある多角形、または PSLG を形成する入力を考慮します。多角形入力の場合、頂点の数をnで表し、反射頂点 (凹面、つまり角度がπより大きい)の数をrで表します。入力が PSLG の場合は、多角形のセットを形成する初期の波面構造を考慮し、頂点の数をnで表し、伝播方向に対する反射頂点の数をrで表します。ここにリストされているアルゴリズムのほとんどは、実際の RAM計算モデル で設計および分析されています。

• Aichholzerら^{[2] [3]は、} PSLGのストレートスケルトンをO( n ³  log  n )、より正確にはO(( n ² + f )log  n )で計算する方法を示しました。ここで、nは入力ポリゴンの頂点数、fは構築中の反転イベントの数です。fの最もよく知られている上限はO ( n ³ )です。
• 最悪実行時間がO( nr  log n)、または単にO( n2log n)のアルゴリズム^は HuberとHeld(2010, 2011)によって提案されており、彼らはこのアプローチが多くの入力に対してほぼ線形時間で実行される可能性が高いと主張している。^{[5] [6]}
• Petr FelkelとŠtěpán Obdržálekは、単純な多角形に対してO( nr + n log r )の効率を持つと言われるアルゴリズムを設計した。 ^{[7] [8]}しかし、彼らのアルゴリズムは誤りであることが示された。^{[9] [10]}
• エップスタインとエリクソンは、二色最近接ペア問題のデータ構造を用いて、最近接ペアデータ構造の線形更新によってストレートスケルトン問題を構築する方法を示した。四分木に基づく最近接ペアデータ構造は、 O( nr  +  n  log  n )時間のアルゴリズムを提供する。または、これよりはるかに複雑なデータ構造は、よりよい漸近的時間境界O( n ^{1 + ε} + n ^{8/11 + ε} r ^{9/11 + ε} )、またはもっと簡単にはO( n ^{17/11 + ε} )につながる。ここで、εはゼロより大きい任意の定数である。^[11]これは、無制限の入力によるストレートスケルトン構築に対する最悪ケースの時間境界として知られているが、複雑であり、実装されていない。
• 一般位置の単純な多角形の場合、直線スケルトンの構築問題はより簡単です。 Cheng、Mencel、および Vigneron は、単純な多角形の直線スケルトンを O( n log n log r + r ^{4/3 + ε} ) の時間で計算する方法を示しました。^[12] 最悪の場合、r はnのオーダーになる可能性があり、その場合、この時間制限は O( n ^{4/3+ε ) に簡略化されます。入力多角形の頂点が O(log n) ビットの有理座標を持つ場合、入力多角形が}一般位置にない場合でも、アルゴリズムを O( n  log  n ) 時間で実行するように改善できます。
• 直線Lに関する単調多角形は、 Lに直交^するすべての直線が単一の区間で多角形と交差するという性質を持つ多角形である。入力が単調多角形の場合、その直線の骨格はO( nlog2n ) の時間で構築できる。^[13] 

入力ポリゴン内の各ポイントは、収縮プロセスがそのポイントに到達した時間をポイントの Z 座標として使用することで、3 次元空間に持ち上げることができます。結果として得られる 3 次元サーフェスは、ポリゴンのエッジ上で一定の高さを持ち、異なる角度のサーフェス パッチが出会う直線スケルトン自体のポイントを除いて、エッジから一定の傾斜で上昇します。このように、直線スケルトンは、最初のポリゴンの形の壁に基づいて、建物の屋根の尾根線のセットとして使用できます。^{[2] [14]}図の下の図は、このようにして直線スケルトンから形成されたサーフェスを示しています。

デメイン、デメイン、ルビウは、直線骨格を、与えられた多角形を1回の直線カットで切り取ることができるように紙を折る技術（折り曲げ切断定理）や、関連する折り紙設計問題の一部として使用しました。^[15]

Barequetらは、与えられた2つの多角形チェーンの間を補間する3次元表面を見つけるアルゴリズムに直線スケルトンを使用しています。^[16]

タナセとヴェルトカンプは、画像処理における形状マッチングの前処理として、直線スケルトンを使用して凹多角形を凸領域の結合に分解することを提案している。 ^[17]

BagheriとRazzaziは、直線状のスケルトンを使用して、グラフ描画が多角形の境界内に制約されるグラフ描画アルゴリズムで頂点の配置をガイドします。 ^[18]

直線スケルトンは、中心軸から丸い角を持つオフセット曲線を構築するのと同様に、斜めの角を持つ多角形のオフセット曲線を構築するためにも使用できます。友枝と杉原は、このアイデアを、広い角度から見え、奥行きがあるように見える標識のデザインに適用しています。 ^[19]同様に、アセンテとカーは、直線スケルトンを使用して、文字のアウトラインやその他の形状に一致する色のグラデーションをデザインしています。^[20]

中心軸などの他のタイプのスケルトンと同様に、ストレートスケルトンは2次元領域を単純化された1次元表現に縮小するために使用できます。たとえば、ハウナートとセスターは、道路の中心線を見つけるために地理情報システムでストレートスケルトンのこのタイプのアプリケーションを説明しています。^{[21] [22]}

次数が2の頂点を持たないすべての木は、凸多角形の直線の骨格として実現できます。^[23]この直線の骨格に対応する屋根の形の凸包は、木の葉を閉路に接続することによって形成されたハリングラフのシュタイニッツ 実現を形成します。

Barequetらは、3次元多面体の直線骨格のバージョンを定義し、それを計算するためのアルゴリズムを記述し、いくつかの異なるタイプの多面体におけるその複雑さを分析しました。^[24]

フーバーらは、対応するボロノイ図と直線スケルトンが一致する距離空間を調査した。2次元の場合、このような距離空間の特徴付けは完全である。高次元の場合、この方法は、ボロノイ図を用いて特定の入力形状の直線スケルトンを任意の次元に一般化するものとして解釈できる。^[25]

• エリックソン、ジェフ。「単純な多角形の直線スケルトン」。
• 計算幾何学アルゴリズムライブラリCGALの 2D ストレート スケルトン
• 穴のあるポリゴン用のストレート スケルトン。Java で実装されたストレート スケルトン ビルダー。
• Amit Parnerkar、Sarnath Ramnath。「O(n log n) で単純な多角形の直線の骨格を見つけるための効率的なアルゴリズムの設計」。
• STALGO: 「STALGO は、直線スケルトンと斜めオフセット曲線を計算するための産業用 C++ ソフトウェア パッケージです。」 (Stefan Huber 著)