Loading article…
計算幾何学において、回転ノギス法は、一連の点の 幅や直径を求めるなどの最適化問題を解決するために使用できるアルゴリズム設計手法です。
この方法は、バネ仕掛けのノギスを凸多角形の外側で回転させる方法に似ていることから、このように名付けられました。[1]ノギスの片方の刃が多角形の端に平らに接するたびに、点または端が反対側の刃に接して対蹠対を形成します。ノギスを多角形の周りで完全に「回転」させると、すべての対蹠対が検出されます。すべての対の集合をグラフとして見ると、トラクルが形成されます。ノギスを回転させる方法は、スイープが点のx座標またはy座標ではなく、直線の傾斜に沿って行われるスイープ ライン アルゴリズムの射影双対として解釈できます。
歴史
回転ノギス法は、1978 年にマイケル シャモスの博士論文で初めて使用されました。[2]シャモスはこの方法を使用して、凸多角形上のすべての対蹠点を生成し、凸多角形の直径を時間内に計算しました。ゴッドフリード トゥーサンは「回転ノギス」というフレーズを作り出し、この方法が他の多くの計算幾何学の問題の解決にも適用できることを実証しました。[3]
シャモスのアルゴリズム
シャモスは、回転キャリパー法の次のようなアルゴリズムを博士論文（pp.77-82）で示しており、凸多角形上のすべての対頂角対を生成する：[2]
/* p[] は標準形式、つまり反時計回りの順序、
異なる頂点、共線上の頂点なしです。ANGLE (m, n) は
、有向線分 Pm,Pm+1 に平行な位置から Pn, Pn+1 に平行な位置まで 回転する光線によって掃引される 時計回りの角度を返すプロシージャです。
すべてのインデックスは mod N に縮小されるものと想定します (したがって、N+1 = 1)。*/ GetAllAntiPodalPairs ( p [ 1. . n ]) // P1 の反対側の頂点を見つけて最初の反対のペアを見つけます。i = 1 j = 2 while angle ( i , j ) < pi j ++ yield i , j
/* 次に、平行なエッジの可能性を考慮してポリゴンの周りを進みます
。線 L は Pi、Pi+1 を通り
、線 M は Pj、Pj+1 を通ります
*/
// P 全体がスキャンされるまで j をループします
。current = i while j != n if angle ( current , i + 1 ) <= angle ( current , j + 1 ) j ++ current = j else i ++ current = i yield i , j
// ここで平行エッジに注意してください
if angle ( current , i + 1 ) = angle ( current , j + 1 ) yield i + 1 , j yield i , j + 1 yield i + 1 , j + 1 if current = i j ++ else i ++
このアルゴリズムの別のバージョンは、1985年にプレパラタとシャモスが角度の計算を回避したテキストに登場しました。[4]
GetAllAntiPodalPairs ( p [ 1. . n ])
i0 = n i = 1 j = i + 1 while ( Area ( i 、i + 1 、j + 1 ) > Area ( i 、i + 1 、j )) j = j + 1 j0 = j while ( i != j0 ) i = i + 1 yield i 、j while ( Area ( i 、i + 1 、j + 1 ) > Area ( i 、i + 1 、j )) j = j + 1 if (( i 、j ) != ( j0 、i0 )) yield i 、j else return if ( Area ( j 、i + 1 、j + 1 ) = Area ( i 、i + 1 、j )) if (( i 、j ) != ( j0 、i0 )) yield i 、j + 1 else yield i + 1 、j
アプリケーション
Pirzadeh [5]は回転ノギス法のさまざまな応用について説明しています。
距離
- 凸多角形の直径（最大幅）[6] [7]
- 凸多角形の幅（最小幅）[8]
- 2つの凸多角形間の最大距離[9] [10]
- 2つの凸多角形間の最小距離[11] [12]
- 2 つの凸多角形間の最も広い空の (または分離する) ストリップ (サポート ベクター マシンベースの機械学習で発生する問題の簡略化された低次元のバリエーション)
- 2つの凸多角形間のグレナンダー距離[13]
- 最適ストリップ分離（医療用画像やソリッドモデリングで使用）[14]
境界ボックス
三角測量
マルチポリゴン操作
- 2つの凸多角形の和
- 2つの凸多角形の共通接線
- 二つの凸多角形の交差[16]
- 2つの凸多角形の重要なサポートライン
- 2つの凸多角形のベクトル和（ミンコフスキー和）[17]
- 2つの凸多角形の凸包
トラバーサル
- 最短横断線[18] [19]
- 最も薄いストリップ横断線[20]
その他
- 機械学習による分類のための非パラメトリック決定ルール[21]
- コンピュータビジョンにおける視認性問題に対する開口角の最適化[22]
- 数百万の生物細胞の中で最も長い細胞を見つける[23]
- 射撃場での二人の精度の比較
- スキャン画像から脳の部分を分類する
参照
参考文献
- ^ Toussaint のホームページの「回転キャリパー」
- ^ ab Shamos, Michael (1978). 「計算幾何学」(PDF) . イェール大学. pp. 76–81.
- ^ Toussaint, Godfried T. (1983). 「回転キャリパーによる幾何学的問題の解決」。Protonotarios, EN; Stassinopoulos, GI; Civalleri, PP (編)。MELECON '83 議事録、地中海電気技術会議、アテネ、ギリシャ、1983 年 5 月 24 ～ 26 日。IEEE。pp . A10.02/1 ～ 4。CiteSeerX 10.1.1.155.5671。
- ^ シャモス、フランコ・P・プレパラタ、マイケル・イアン (1985)。計算幾何学入門。ニューヨーク州ニューヨーク: スプリンガー ニューヨーク。ISBN 978-1-4612-7010-2。
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク) - ^ Pirzadeh, Hormoz (1999). 回転キャリパーによる計算幾何学 (修士論文). マギル大学.
- ^ Binay K. Bhattacharya および Godfried T. Toussaint、「有限平面集合の直径を計算するための高速アルゴリズム」、The Visual Computer、Vol. 3、No. 6、1988 年 5 月、pp.379–388。
- ^ Binay K. Bhattacharya および Godfried T. Toussaint、「凸多角形の直径アルゴリズムに対する反例」、IEEE Transactions on Pattern Analysis and Machine Intelligence、Vol. PAMI-4、No. 3、1982 年 5 月、pp. 306–309。
- ^ Michael E. Houle および Godfried T. Toussaint、「セットの幅の計算」、IEEE Transactions on Pattern Analysis & Machine Intelligence、第 10 巻、第 5 号、1988 年 9 月、761 ～ 765 ページ。
- ^ Godfried T. Toussaint および Jim A. McAlear、「 2 つの有限平面集合間の最大距離を見つけるための単純な O( n log n ) アルゴリズム」、 Pattern Recognition Letters、第 1 巻、1982 年、21 ～ 24 ページ。
- ^ Binay K. Bhattacharya および Godfried T. Toussaint、「2 つの有限平面集合間の最大距離を計算するための効率的なアルゴリズム」、Journal of Algorithms、vol. 14、1983 年、pp. 121–136。
- ^ Godfried T. Toussaint および Binay K. Bhattacharya、「2 つの有限平面セット間の最小距離を計算するための最適アルゴリズム」 、 Pattern Recognition Letters、第 2 巻、1983 年 12 月、79 ～ 82 ページ。
- ^ “回転キャリパー”. 2015年3月30日. 2015年3月30日時点のオリジナルよりアーカイブ。2017年3月22日閲覧。
{{cite web}}: CS1 maint: bot: 元の URL ステータス不明 (リンク) - ^ MARTINEZ, HUGO M. (1978 年 1 月 1 日)。「U. Grenander 著『PATTERN SYNTHESIS』のレビュー、Springer-Verlag、ニューヨーク、1976 年、509 ページ」。International Journal of General Systems。4 ( 2): 126–127。doi : 10.1080 /03081077808960672。ISSN 0308-1079 。
- ^ Barequet and Wolfers (1998). 「2つのポリゴンを分離するストリップの最適化」グラフィカルモデルと画像処理60 ( 3): 214–221. doi : 10.1006/gmip.1998.0470 .
- ^ Teichmann, Marek (1989). ウェッジ配置最適化問題 (修士論文). マギル大学.
- ^ Godfried T. Toussaint、「交差凸多角形の単純な線形アルゴリズム」、The Visual Computer、第 1 巻、1985 年、118 ～ 123 ページ。
- ^ Tomas Lozano-Perez、「空間計画: 構成空間アプローチ」、IEEE Transactions on Computers、Vol. 32、No. 2、1983 年、108 ～ 120 ページ。
- ^ Binay K. Bhattacharya および Godfried T. Toussaint、「最短横断計算」、Computing、vol. 46、1991 年、93 ～ 119 ページ。
- ^ Binay K. Bhattacharya、Jurek Czyzowicz、Peter Egyed、Ivan Stojmenovic、Godfried T. Toussaint、Jorje Urrutia、「集合の最短横断の計算」、International Journal of Computational Geometry and Applications、第2巻、第4号、1992年12月、417～436ページ。
- ^ Jean-Marc Robert および Godfried T. Toussaint、「単純なオブジェクトの線形近似」、計算幾何学: 理論と応用、第 4 巻、1994 年、27 ～ 52 ページ。
- ^ Rasson and Granville (1996). 「分類における幾何学的ツール」.計算統計とデータ分析. 23 (1): 105–123. doi :10.1016/S0167-9473(96)00024-2.
- ^ Bose, P.; Hurtado-Diaz, F.; Omaña-Pulido, E.; Snoeyink, J.; Toussaint, GT (2002-08-01). 「いくつかの開口角最適化問題」. Algorithmica . 33 (4): 411–435. CiteSeerX 10.1.1.16.7118 . doi :10.1007/s00453-001-0112-9. ISSN 0178-4617. S2CID 27455160.
- ^ 「凸多角形の直径アルゴリズムが正しくない」。