algorithm - 2次元配列を反時計回りに印刷

Question

配列を反時計回りに印刷するにはどうすればよいですか? 有名な「配列をらせん状に印刷する」アルゴリズムは知っていますが、反時計回りに印刷する方法を見るのは興味深いでしょう

Answer 1

2次元座標の配列を考えていると仮定すると...

基本的に、y座標とx座標の商のatnで配列をソートし、順番に出力する必要があります。高価で数値的に不安定な演算を回避しながら、極と符号の変更を適切に処理すると、実装が複雑になります。次の疑似コードは、原則を説明するのに役立ちます。

ポイント セットは 0 から 8 までの番号が付けられた 9 つのカテゴリに分割されます。#0 には(0,0)最初に出力されるポイントが含まれ、#1,3,5,7 には正の y 軸、負の x 軸、負の y 軸、および正の x 上のポイントが含まれます。軸、それぞれ。これらの各カテゴリ内で、ポイントは原点からの距離が大きくなる順に出力されます。カテゴリ #2、4、6、8 には、それぞれ第 2、第 3、第 4、および第 1 象限からのポイントが含まれます。これらの各カテゴリ内で、ポイントは反時計回りに印刷されます。原点から同じベクトル上にあるポイントは、原点からの距離が大きくなる順に印刷されます。

a:array of point(x:number,y:number)あなたの配列にしましょう。f:array of (f1:number, f2:number, f3:number)コンポーネントごとに次のように定義します

f[i].f1 :=
    let x := a[i].x, y := a[i].y;
    if x=0 then
        if y=0 then
            0
        else
            if y>0 then 1 else 5
        endif
    else
        if y=0 then
            if x>0 then 7 else 3
        else
            if x>0 and y>0 then
                8
            elsif x>0 and y<0 then
                6
            elsif x<0 and y<0 then
                4
            else
                2
            endif
        endif
    endif;

f[i].f2 :=
    let x := a[i].x, y := a[i].y, h := f[i].f1;
    if odd(h) then
        abs(x) + abs(y)
    else
        if h=0 then
            0
        elsif h=2 then
            -x/y
        elsif h=4 then
            y/x
        elsif h=6 then
            -x/y
        else
            y/x
        endif
    endif;

f[i].f3 :=
    a[i].x * a[i].x + a[i].y * a[i].y;

お気に入りの並べ替えアルゴリズムを適用して、a辞書順で昇順に並べ替えf.f1, f.f2, f.f3、結果を順番に出力します。