ストレートスケルトン
幾何学において、多角形を位相的な骨格で表現する方法

縮む過程、真っ直ぐな骨組み（青）と屋根の模型。

幾何学において、直線スケルトンとは、位相スケルトンを用いて多角形を表現する手法である。これは中軸といくつかの点で類似しているが、スケルトンが直線分で構成されるのに対し、多角形の中軸は放物曲線を含む場合があるという点で異なる。しかし、どちらも基となる多角形とホモトピー同値である。[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 3  log  n )、より正確にはO(( n 2 + f ) log  n )で計算する方法を示した。ここで、nは入力ポリゴンの頂点数、fは構築中の反転イベント数である。fの最もよく知られている上限値はO ( n 3 )である。
  • 最悪実行時間がO( nr  log n)、または単にO( n2log n)のアルゴリズムはHuberとHeld(2010, 2011)によって提案されており、彼らはこのアプローチが 多くの入力に対してほぼ線形時間で実行されると主張している。[5] [6]
  • ペトル・フェルケルとシュテパン・オブドゥルジャレックは、単純な多角形に対して、O( nr + nlogr )の効率を持つと言われるアルゴリズムを設計した。[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( n  log 2 n )の時間で構築できる。[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らは、三次元多面体の直線骨格のバージョンを定義し、それを計算するためのアルゴリズムを記述し、いくつかの異なるタイプの多面体におけるその複雑さを分析した。[24]

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

参考文献

  1. ^ Huber, Stefan (2018). 「スケルトンとオフセットのトポロジー」(PDF) .第34回ヨーロッパ計算幾何学ワークショップ (EuroCG'18) の議事録.。
  2. ^ abc アイヒ ホルツァー、オズウィン; Aurenhammer, フランツ;アルバーツ、デイビッド。ゲルトナー、ベルント (1995)。 「ポリゴン用の新しいタイプのスケルトン」。ユニバーサルコンピュータサイエンスジャーナル。1 (12): 752–761。土井:10.1007/978-3-642-80350-5_65。MR1392429  。。
  3. ^ ab Aichholzer, Oswin; Aurenhammer, Franz (1996). 「平面上の一般多角形図形の直線スケルトン」Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON '96) . Lecture Notes in Computer Science. Vol. 1090. Springer-Verlag. pp.  117– 126.
  4. ^ ペシュカ、グスタフ A. (1877)。 Kotirte Ebenen: Kotirte Projektionen und deren Anwendung;ヴォルトレゲ。ブリュン：ブッシュチャクとイルガング。土井:10.14463/GBV:865177619。。
  5. ^ Huber, Stefan; Held, Martin (2010). 「オートバイグラフに基づく平面直線グラフの直線スケルトンの計算」(PDF) .第22回カナダ計算幾何学会議議事録.。
  6. ^ Huber, Stefan; Held, Martin (2011). 「平面直線グラフの直線スケルトンに関する理論的および実際的な結果」(PDF) .第27回計算幾何学シンポジウム (SCG'11) の議事録, 2011年6月13～15日, フランス, パリ. pp.  171– 178.。
  7. ^ "CenterLineReplacer". FME Transformers . Safe Software . 2013年8月5日閲覧。。
  8. ^ フェルケル、ペトル;オブドルジャーレク、シュテパン (1998)。 「ストレートスケルトン実装」。SCCG 98: コンピュータ グラフィックスに関する第 14 回春季会議の議事録。210～ 218ページ 。。
  9. ^ Huber, Stefan (2012). Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice. Shaker Verlag. ISBN 978-3-8440-0938-5。。
  10. ^ Yakersberg, Evgeny (2004).直線スケルトンベースの補間を用いた幾何学的形状間のモーフィング. イスラエル工科大学.。
  11. ^ Eppstein, David ; Erickson, Jeff (1999). 「屋根を高くする、サイクルをクラッシュさせる、そしてビリヤードをする：ペアワイズ相互作用を見つけるためのデータ構造の応用」.離散幾何学と計算幾何学. 22 (4): 569– 592. doi : 10.1007/PL00009479 . MR  1721026. S2CID  12460625.。
  12. ^ Cheng, Siu-Wing; Mencel, Liam; Vigneron, Antoine (2016). 「ストレートスケルトンを計算するための高速アルゴリズム」. ACM Transactions on Algorithms . 12 (3): 44:1–44:21. arXiv : 1405.4691 . doi :10.1145/2898961. 。
  13. ^ Biedl, Therese ; Held, Martin ; Huber, Stefan ; Kaaser, Dominik ; Palfrader, Peter (2015年2月). 「単調多角形の正の重み付き直線スケルトンを計算するための単純なアルゴリズム」(PDF) . Information Processing Letters . 115 (2): 243– 247. doi :10.1016/j.ipl.2014.09.021. PMC 4308025 . PMID  25648376. Biedlらが指摘するように、Dasらによる単調多角形用の以前のアルゴリズムは記述されている通り誤りであり、せいぜい頂点間イベントを含まない一般位置の入力に対してのみ有効である： Das, Gautam K.; Mukhopadhyay, Asish; Nandy, Subhas C.; Patil, Sangameswar; Rao, SV (2010). 「単調多角形の直線スケルトンをO(n log n)時間で計算する」(PDF) . Proceedings of the 22nd Canadian Conference on Computational Geometry .。
  14. ^ ベランジェ、ダヴィッド（2000年）『建物の屋根の設計』。
  15. ^ Demaine, Erik D. ; Demaine, Martin L. ; Lubiw, Anna (1998). 「紙の折り方と切り方」.離散幾何学と計算幾何学に関する日本会議 (JCDCG'98) の改訂論文集. 計算機科学講義ノート. 第1763巻. Springer-Verlag. pp.  104– 117. doi :10.1007/b75044. ISBN 978-3-540-67181-7. S2CID  32962663。。
  16. ^ Barequet, Gill; Goodrich, Michael T .; Levi-Steiner, Aya; Steiner, Dvir (2003). 「ストレートスケルトンベースの輪郭補間」.第14回ACM-SIAM離散アルゴリズムシンポジウム論文集. pp.  119– 127.。
  17. ^ Tănase, Mirela; Veltkamp, Remco C. (2003). 「直線スケルトンに基づくポリゴン分解」.第19回ACM計算幾何学シンポジウム論文集. pp.  58– 67. doi :10.1145/777792.777802. ISBN 1-58113-663-3. S2CID  18173658。。
  18. ^ Bagheri, Alireza; Razzazi, Mohammadreza (2004). 「ポリゴンスケルトンを用いた単純なポリゴン内部への自由樹木の描画」. Computing and Informatics . 23 (3): 239– 254. MR  2165282.。
  19. ^ 友枝明康、杉原厚吉 (2012). 「新しい錯視的立体記号の計算的生成」.第9回科学技術におけるボロノイ図に関する国際シンポジウム (ISVD 2012) . pp.  144– 147. doi :10.1109/ISVD.2012.26. ISBN 978-1-4673-1910-2. S2CID  27610348。。
  20. ^ Asente, Paul; Carr, Nathan (2013). 「3Dベベルを用いた輪郭線グラデーションの作成」. Proceedings of the Symposium on Computational Aesthetics (CAE '13, Anaheim, California) . New York, NY, USA: ACM. pp.  63– 66. doi :10.1145/2487276.2487283. ISBN 978-1-4503-2203-4. S2CID  17302186。。
  21. ^ Haunert, Jan-Henrik; Sester, Monika (2008). 「直線スケルトンに基づくエリア崩壊と道路中心線」. GeoInformatica . 12 (2): 169– 191. doi :10.1007/s10707-007-0028-x. S2CID  2169666.。
  22. ^ Raleigh, David Baring (2008). GPS粗取得データを用いた道路中心線の直線スケルトン測量調整：ボリビアにおける事例研究. オハイオ州立大学、測地科学・測量学部.。
  23. ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012). 「木をまっすぐな骨格にするものは何か？」(PDF) .第24回カナダ計算幾何学会議 (CCCG'12) の議事録.。
  24. ^ Barequet, Gill; Eppstein, David ; Goodrich, Michael T .; Vaxman, Amir (2008). 「3次元多面体の直線スケルトン」. Proc. 16th European Symposium on Algorithms . Lecture Notes in Computer Science. Vol. 5193. Springer-Verlag. pp.  148– 160. arXiv : 0805.0022 . doi :10.1007/978-3-540-87744-8_13. ISBN 978-3-540-87743-1. S2CID  42150。。
  25. ^ Huber, Stefan; Aichholzer, Oswin; Hackl, Thomas; Vogtenhuber, Birgit (2014). 「多面体距離関数におけるボロノイ図を用いた直線スケルトン」(PDF) .第26回カナダ計算幾何学会議 (CCCG'14) 講演論文集.。
  • エリックソン、ジェフ。「単純な多角形の直線スケルトン」。
  • 計算幾何学アルゴリズムライブラリCGALの 2D ストレートスケルトン
  • 穴のあるポリゴンのストレート スケルトン。ストレート スケルトン ビルダーは Java で実装されています。
  • Amit Parnerkar、Sarnath Ramnath。「単純な多角形の直線の骨格をO(n log n)で見つける効率的なアルゴリズムの設計」
  • STALGO: 「STALGO は、直線スケルトンと斜めオフセット曲線を計算するための産業用 C++ ソフトウェア パッケージです。」 (Stefan Huber 著)
「https://en.wikipedia.org/w/index.php?title=Straight_skeleton&oldid=1242871491」より取得