かいてんチャツク
http://blog.csdn.net/ACMaker/archive/2008/10/29/3176910.aspx
http://cgm.cs.mcgill.ca/~orm/rotcal.frame.html
履歴:
1978年、M.I.Shamos's Ph.D.の論文「Computational Geometry」はコンピュータ科学のこの分野の誕生を示した.当時彼が発表した成果は,凸多角形の直径を探す非常に簡単なアルゴリズムであり,すなわち多角形の一対の点距離の最大値に基づいて決定した.その後,直径は一対の踵点対によって決定された.Shamosは,凸n角形の対踵点対を決定する簡単なO(n)時間アルゴリズムを提案した.彼らは最大3 n/2対しかないので,直径はO(n)時間で算出できる.Toussaintが後に提案したように,Shamosのアルゴリズムは多角形の周りに一対のカードシェルを回転させるようなものである.そのため、「回転ハウジング」という用語があります.1983年、Toussaintは同じ技術で多くの問題を解決する論文を発表した.以来,このモデルに基づく新しいアルゴリズムが確立され,多くの問題が解決された.次のようなものがあります.計算距離 凸多角形直径 凸多角形幅 凸多角形間最大距離 凸多角形間最小距離 外接矩形 最小面積外接矩形 最小周長外接矩形 三角断面 玉ねぎ三角断面 螺旋三角断面 四角形断面 凸多角形アトリビュート 合併凸包 共通接線 を探します凸多角形交 臨界接線 凸多角形ベクトルと 最薄断面 最薄横断帯
凸多角形の直径1つの多角形上の任意の2点間の距離の最大値を多角形の直径として定義します.この直径を決定する点対数は1対より多い可能性がある.実際には
n個の頂点の多角形は、
n対の「直径点対」が存在する.
ポリゴンの直径の簡単な例を左図に示します.直径点対は、平行線が通る黒点(赤色の一対の平行線)として図中に示す.直径は水色でハイライト表示されます.
凸多角形を決定するのは明らかです
P直径の点対が多角形にあるはずがない
P内部.したがって、検索は境界上で行うべきです.実際、直径は多角形の平行接線の最も遠い距離によって決まるので、クエリーだけが必要です.
踵を合わせる.Shamos(1978)は
O(n)時間複雑度n点バンプ対踵点対を計算するアルゴリズム.直径は頂点リストを巡回することで最大距離を得ることができます.以下は1985年にPreparataとShamosの文書に発表されたShamosアルゴリズムの擬似コードである.
入力は多角形
P={
p1,...,
pn}.
ここ
(p,q)対踵点対出力として、
pqrの有向面積.
この過程は従来の回転シェルアルゴリズムとは直感的に異なるが,本質的に同じであり,すべての角度の計算を回避した.
以下に、より直感的なアルゴリズムを示します.多角形y方向の端点を計算する.私たちはyminとymaxと呼ばれています. は、yminとymaxによって2つの水平接線を構築する.彼らはすでに一対の踵点であるため、彼らの間の距離を計算し、現在の最大値に維持します. は、2つの線を同時に回転させ、そのうちの1つが多角形の1つのエッジと重なるまで回転させる. 新しい対踵点対がこのとき生成される.新しい距離を計算し、現在の最大値と比較し、現在の最大値より大きい場合に更新します. ステップ3およびステップ4のプロセスは、踵対(ymin,ymax)が再び生成されるまで繰り返される. 出力は、最大直径の対踵点対を決定する.
これにより,上述したプロセス(擬似コードの)は非常に有用であり,多角形の
幅.
http://cgm.cs.mcgill.ca/~orm/rotcal.frame.html
履歴:
1978年、M.I.Shamos's Ph.D.の論文「Computational Geometry」はコンピュータ科学のこの分野の誕生を示した.当時彼が発表した成果は,凸多角形の直径を探す非常に簡単なアルゴリズムであり,すなわち多角形の一対の点距離の最大値に基づいて決定した.その後,直径は一対の踵点対によって決定された.Shamosは,凸n角形の対踵点対を決定する簡単なO(n)時間アルゴリズムを提案した.彼らは最大3 n/2対しかないので,直径はO(n)時間で算出できる.Toussaintが後に提案したように,Shamosのアルゴリズムは多角形の周りに一対のカードシェルを回転させるようなものである.そのため、「回転ハウジング」という用語があります.1983年、Toussaintは同じ技術で多くの問題を解決する論文を発表した.以来,このモデルに基づく新しいアルゴリズムが確立され,多くの問題が解決された.次のようなものがあります.
凸多角形の直径1つの多角形上の任意の2点間の距離の最大値を多角形の直径として定義します.この直径を決定する点対数は1対より多い可能性がある.実際には
n個の頂点の多角形は、
n対の「直径点対」が存在する.
ポリゴンの直径の簡単な例を左図に示します.直径点対は、平行線が通る黒点(赤色の一対の平行線)として図中に示す.直径は水色でハイライト表示されます.
凸多角形を決定するのは明らかです
P直径の点対が多角形にあるはずがない
P内部.したがって、検索は境界上で行うべきです.実際、直径は多角形の平行接線の最も遠い距離によって決まるので、クエリーだけが必要です.
踵を合わせる.Shamos(1978)は
O(n)時間複雑度n点バンプ対踵点対を計算するアルゴリズム.直径は頂点リストを巡回することで最大距離を得ることができます.以下は1985年にPreparataとShamosの文書に発表されたShamosアルゴリズムの擬似コードである.
入力は多角形
P={
p1,...,
pn}.
begin
p0:=pn;
q:=NEXT[p];
while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q)) do
q:=NEXT[q];
q0:=q;
while (q != p0) do
begin
p:=NEXT[p];
Print(p,q);
while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q) do
begin
q:=NEXT[q];
if ((p,q) != (q0,p0)) then Print(p,q)
else return
end;
if (Area(p,NEXT[p],NEXT[q]) = Area(p,NEXT[p],q)) then
if ((p,q) != (q0,p0)) then Print(p,NEXT[q])
else Print(NEXT[p],q)
end
end.
ここ
Print(p,q)は(p,q)対踵点対出力として、
Area(p,q,r)は三角形を表すpqrの有向面積.
この過程は従来の回転シェルアルゴリズムとは直感的に異なるが,本質的に同じであり,すべての角度の計算を回避した.
以下に、より直感的なアルゴリズムを示します.
これにより,上述したプロセス(擬似コードの)は非常に有用であり,多角形の
幅.