格子点の列挙 in JavaScript DouKaku?

格子点の列挙

二次元平面上の格子点(X,Y座標がともに整数の点)を、原点から近い順に列挙してください。

同じ距離の点はどういう順番でも構いませんが、可能であればX軸に一番近い第一象限の点から原点を中心として反時計回りの順に列挙してください。列挙の方法は、1行に一つの点の、X,Y座標を出力することとします。

サンプル出力

0, 0
1, 0
0, 1
-1, 0
0, -1
1, 1
-1, 1
1, -1
-1, -1
2, 0

最低でも1000件まで列挙できることを確認してください。また「反時計回り」の条件も満たしている場合は、1000番目の頂点が何かも併せて答えてください。

このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。

Perl がなかったので。力技。

use strict;

my $PI = atan2(1, 1) * 4;
my $MAXR = int(sqrt(1000 / $PI) + sqrt(2) + 0.5);
my @res = ();

for (my $i = 0; $i <= $MAXR; $i++) {
    for (my $j = 0; $j <= $MAXR; $j++) {
        my $r = sqrt($i * $i + $j * $j);
        push(@res, [$i, $j, $r, atan2($j, $i)]);
        ($i != 0) && push(@res, [-$i, $j, $r, atan2($j, -$i)]);
        ($j != 0) && push(@res, [$i, -$j, $r, atan2(-$j, $i) + 2 * $PI]);
        ($i * $j != 0) && push(@res, [-$i, -$j, $r, atan2(-$j, -$i) + 2 * $PI]);
    }
}

foreach my $p (sort {($a->[2] <=> $b->[2]) || ($a->[3] <=> $b->[3])} @res) {
    printf("%3d, %3d\n", splice(@{$p}, 0, 2));
}

post comment

Posted feedbacks - JavaScript

原点からの距離(の二乗)と角度でソート。
これだけだと二番煎じなので，出力をドリトルのソース(実行するとカメが格子点を辿る)にしてみました。

see: プログラミング言語「ドリトル」

function doukaku65(n){
  with(Math) for(var p = [], i = 0, m = sqrt(n/2)|0, y, x = -m; x <= m; x++) for(y = -m; y <= m; y++)
    (p[i++] = [x, y]).keys = [x*x + y*y, atan(y/x) + PI * (x < 0 ? 1 : y < 0 ? 2 : 0)];
  return p.sort(function(a, b){ return a.keys[0] - b.keys[0] || a.keys[1] - b.keys[1] }).splice(0, n);
}
var i = 1000;
(this.print || this.WSH && function($){ WSH.echo($) } || this.document && document.write)
  ('//<pre>\n'+
   '亀＝タートル！作る 1 線の太さ。'+
   '点＝配列！\n'+ doukaku65(i).join('\n').replace(/,/g, ' ') +'\n作る。'+
   'タイマー！作る '+ 1/i +' 間隔 '+ i + ' 回数'+
   '「｜回｜亀！((点！(回＊２－１)見る)＊10)((点！(回＊２)見る)＊10)位置」実行。'+
   '\n//</pre>');

DouKaku?

格子点の列挙

Posted feedbacks - JavaScript

Index

Feed

Other

Link

Pathtraq