

3次元空間において、r = (x, y, z)を1点決めて、  
これを中心とした半径nの球を考えます。  
次に、この球の内部をグリッドで細かく立方体に分割します。  
この立方体の辺の長さはmとします。  
このとき、グリッドの交点の座標をすべて計算したいです。

やりたいことのイメージは、3次元の球で図を書くのが難しいので、  
2次元の円で図を書きました。以下がそれです。  
グリッドの交点の座標（赤色の点）をすべて求めたいです。

[![](https://i.stack.imgur.com/8CYqE.jpg)](https://i.stack.imgur.com/8CYqE.jpg)

このようなことを実現するコードは、Pythonでどのように書けば良いでしょうか？  
for文で座標をmずつずらすのをぜんぶ書けば良さそうだと思ったのですが、  
球体だと効率的に書くのが思ったより難しい気がしました。

どなたかご教授いただけるとありがたいです。


CC BY-SA 3.0
2017-12-28T15:43:11.640
40592
2018-01-14T06:19:00.190
2018-01-14T06:19:00.190
754
25649
question
python アルゴリズム
球内のグリッドの交点の座標をすべて求めたい


簡単のために`r=(0,0,0)`の場合を考えると、擬似コードで書くとこうすればできるのではないでしょうか。(`abs`は絶対値、`i,j,k`は整数)

[code]

    for i s.t. abs(i*m) <= n:
        for j s.t. abs(j*m) <= (n**2 - (i*m)**2)^(1/2):
            for k s.t. abs(k*m) <= (n**2 - (i*m)**2 - (j*m)**2)^(1/2):
                print(im, jm, km)
    
[/code]

逆に言うとこれ以上高速化するには並列処理するぐらいしかないと思います。


CC BY-SA 3.0
2017-12-28T16:41:20.890
40593
2017-12-28T16:46:27.083
2017-12-28T16:46:27.083
20206
20206
40592
answer


for のループ回数と掛け算の回数を減らして、代わりに set の操作を使ってみました。  
どちらが効率が良いかは計測してないのでわかりません。

[code]

    import math
    
    X = 10
    Y = 15
    Z = 20
    
    n = 10
    m = 4
    
    points = set()
    
    # 0<=x<=y<=z の座標を列挙
    vals = list(map(lambda i: i * m, range(n // m + 1)))
    for xi, x in enumerate(vals):
        for yi, y in enumerate(vals[xi:]):
            for zi, z in enumerate(vals[yi:]):
                if x * x + y * y + z * z <= n * n:
                    points.add((x, y, z))
    
    # x, y, z の座標を入れ替えても球の中にある
    #points |= set(map(lambda p: (p[0], p[1], p[2]), points))
    points |= set(map(lambda p: (p[0], p[2], p[1]), points))
    points |= set(map(lambda p: (p[1], p[2], p[0]), points))
    points |= set(map(lambda p: (p[1], p[0], p[2]), points))
    points |= set(map(lambda p: (p[2], p[0], p[1]), points))
    points |= set(map(lambda p: (p[2], p[1], p[0]), points))
    
    # x, y, z の符号を反転させても球の中にある
    points |= set(map(lambda p: ( p[0],  p[1], -p[2]), points))
    points |= set(map(lambda p: ( p[0], -p[1],  p[2]), points))
    points |= set(map(lambda p: (-p[0],  p[1],  p[2]), points))
    
    # 中心を移動
    points = [ ( p[0] + X, p[1] + Y, p[2] + Z ) for p in points ]
    
    print(points)
    
[/code]


CC BY-SA 3.0
2017-12-28T17:46:46.200
40595
2017-12-28T17:46:46.200
5288
40592
answer