1

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

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

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

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

4
  • 「グリッドの交点の座標」とは図でいうと円と点線の交点で、座標は(m,0,0)などを基底とする、すなわち図ではyの成分はn/mということでしょうか
    – packet0
    Commented 2017年12月28日 16:01
  • コメントありがとうございます。グリッドの交点の座標は、図で言うと、赤色の点すべてです。本文に補足しておきます。中心 r =(x, y)から、x軸あるいはy軸にmずつ移動している感じです。
    – neco
    Commented 2017年12月28日 16:43
  • 1
    質問は単に点を求める方法ですか?それともそれを効率的に求める方法ですか?後者であれば基本となるコードやアルゴリズムを追記したほうが回答がつきやすくなると思います。
    – letrec
    Commented 2017年12月28日 16:58
  • コメントありがとうございます。今のところ、単に点を求める方法だけで充分です。
    – neco
    Commented 2017年12月28日 17:23

2 件の回答 2

1

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

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)

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

1
  • ありがとうございます。自分でPythonコードで書いてみて、確かめてみます。
    – neco
    Commented 2017年12月28日 17:24
1

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

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)
1
  • ありがとうございます。たしかに、座標の入れ替えや符号の反転を考えてコードを書くと、いい感じに処理の回数を減らせるかもです。試してみます。
    – neco
    Commented 2017年12月29日 1:01

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。