格子点の列挙
Perl がなかったので。力技。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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));
}
|
Posted feedbacks - Ruby
1000番目は[1250,-1250]かな？ [[0, 0], [1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [-1, 1], [-1, -1], ...]
1 2 3 4 5 6 7 8 9 10 11 12 | def lattice(limit)
ary = [[0,0]]
i = 1
n = 1
while i < limit
ary << [n,0] << [0,n] << [-n,0] << [0,-n]
ary << [n,n] << [-n,n] << [-n,-n] << [n,-n]
i+=8
n+=1
end
ary
end
|
距離、反時計回り（0-360°）の順にソートするために、setOrder(x,y)中で、角度/360を小数部にセットしています。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | include Math
def gridPoint(limit)
r = []
n = sqrt(2*limit).to_i / 2 #--- search square size
(-n..n).each {|x|
(-n..n).each {|y|
r << [x, y]
}}
r.sort_by {|x, y|setOrder(x, y)}
end
def setOrder(x,y)
deg = atan2(y, x) * 180 / PI
deg += 360 if deg < 0 #--- degree correct
x**2 + y**2 + deg / 360 #--- distance + degree/360
end
limit = 1000
k = gridPoint(limit)
(0..limit).each {|i|
p k[i]
}
|
あえて三角関数atan2を使わずに、n象限の点に評価値n.xxx(xxx=0〜1未満)を設定。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | include Math
def gridPoint(limit, r = [])
n = sqrt(2 * limit).to_i / 2 #--- search square size
(-n..n).each {|x|
(-n..n).each {|y|
r << [x, y]
}}
r.sort_by {|x, y|setOrder(x, y)}
end
def setOrder(x, y, r = 1)
while (x <= 0 || y < 0) && ([x, y] != [0, 0])
x, y = y, -x
r += 1
end
(r += y / (x + y + 1.0)) / 4 + (x**2 + y**2)
end
limit = 1000
p gridPoint(limit)[limit - 1] # -> [-8, 16]
|
充分な数サンプリングしていることを証明していないので, そこが問題点として残っていますが.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | require 'matrix'
include Math
N = 1000
class Vector
include Enumerable #for all?
def x; self[0]; end
def y; self[1]; end
def each; size.times{|i| yield self[i]} end
def rot(rad)
Vector[self[0]*cos(rad)-self[1]*sin(rad), self[1]*cos(rad)+self[0]*sin(rad)]
end
end
def gen_rot_vectors(v)
Array.new(4){|i| v.rot(PI*i.quo(2)).map{|e| e.round}}
end
n = 0
n += 1 while n**2*PI < N #グリッドを十分な数生成するため
Array.new(n){|x| Array.new(n){|y| Vector[x, y]}}.flatten. # 第1象限内でベクトルを生成.
delete_if{|v| v.y == 0 unless v.x == 0}. # 重複を避けるため原点を除くy軸上の点を削除
sort{|a,b| a.r == b.r ? a.x <=> b.x : a.r <=> b.r}.
map{|v| v.all?{|e| e == 0} ? v : gen_rot_vectors(v)}. #原点以外のとき回転ベクトルを生成
flatten.map{|v| v.to_a}[0..N-1].each{|e| p e}
|
すみません. 先程の投稿の修正です. 充分なグリッド数のサンプリングには, サンプリング が最低必要なグリッド数Nを含む正方形に外接す る円を考え, それが内接している, 正方形グリッドを 考えればいいので, 16, 17行目は, n = (sqrt(2)*sqrt(N).ceil).ceil とするべきでした. ceilメソッドを二度も使いたくない方には, n = ((2+sqrt(2))*sqrt(N)).truncate がお勧めです.
かも
#3421()
Rating0/2=0.00
同じ距離の点はどういう順番でも構いませんが、可能であればX軸に一番近い第一象限の点から原点を中心として反時計回りの順に列挙してください。 列挙の方法は、1行に一つの点の、X,Y座標を出力することとします。
サンプル出力
最低でも1000件まで列挙できることを確認してください。 また「反時計回り」の条件も満たしている場合は、1000番目の頂点が何かも併せて答えてください。
このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。
1 reply [ reply ]