I want to find all the coordinates of the intersection of the grid in the sphere.

In a three-dimensional space, set r=(x,y,z) by one point and
Consider a sphere with a radius of n centered around it.
The inside of this sphere is then divided into cubes in a grid.
The side length of this cube is m.
At this time, I would like to calculate all the coordinates of the grid intersection.

The image of what you want to do is difficult to draw a diagram with a three-dimensional sphere, so
I drew a diagram in a two-dimensional circle.Here's what it is.
I'd like to find all the coordinates (red dots) of the grid intersection.

How should I write the code to achieve this in Python?
I thought it would be better to write all the coordinates shifted by m in the for sentence.
I think it's harder to write efficiently with spheres than I thought.

I would appreciate it if someone could tell me.

python algorithm

2022-09-30 21:29

2 Answers

Considering the case of r=(0,0,0) for simplicity, wouldn't it be possible to write in pseudo-code like this?(abs is an absolute value, i,j,k is an integer)

for is.t.abs(i*m)<=n:
    for js.t.abs(j*m)<=(n**2-(i*m)**2)^(1/2):
        forks.t.abs(k*m)<=(n**2-(i*m)**2-(j*m)**2)^(1/2):
            print(im,jm,km)

On the other hand, I think the only way to speed it up is to process it in parallel.

2022-09-30 21:29

I reduced the number of loops and multiplication of for and tried using the set operation instead.
I don't know which one is more efficient because I didn't measure it.

import path

X = 10
Y = 15
Z = 20

n = 10
m = 4

points = set()

# Enumerate coordinates of 0<=x<=y<=z
vals=list(map(lambdai:i*m, range(n//m+1))))
for xi, x in enumerate (vals):
    for yi, yin enumerate (vals[xi:]):
        for zi, zin enumerate (values[yi:]):
            if x*x+y*y+z*z<=n*n:
                points.add((x,y,z))

# The coordinates of x, y, and z are still in the sphere.
# points | = set (map(lambdap:(p[0], p[1], p[2]), points))
points | = set (map(lambdap:(p[0], p[2], p[1], points))
points | = set (map(lambdap:(p[1], p[2], p[0], points))
points | = set (map(lambdap:(p[1], p[0], p[2], points))
points | = set (map(lambdap:(p[2], p[0], p[1], points))
points | = set (map(lambdap:(p[2], p[1], p[0], points))

# be in the sphere even if the signs x, y, and z are reversed
points | = set (map(lambdap:(p[0], p[1], -p[2], points))
points | = set (map(lambdap:(p[0], -p[1], p[2]), points))
points | = set (lambdap: (-p[0], p[1], p[2], points))

# Move the center
points = [(p[0]+X,p[1]+Y,p[2]+Z)for pin points]

print(points)

2022-09-30 21:29

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656