What is the formula for creating an n-dimensional grid from a 1-dimensional loop?

user_5534232 0
Viewed 65

I'm trying to create a 3D grid of Node types (a custom data-type).

To create a 2D grid, I usually use this formula:
where i is the current iteration in 1D loop, and gridsize is size of one axis of grid

x = i % gridsize,  
y = floor(i / gridsize)

For example, in Python:

from math import floor

grid = list()
gridsize = 3       # 3x3 grid

for i in range(gridsize**2):
    x = i % gridsize
    y = floor(i / gridsize)
    grid.append( Node(x, y) )

How can I alter this formula to find x, y, and z coordinates for a 3D grid, and is there a general rule for finding coordinates for nD grids?

math python
3 Answers

Afer writing out a table of x, y and z values for a 3x3x3 grid, I figured this out:

For a cubic 3D¹ grid

x = i % gs
y = floor(i / gs) % gs
z = floor(i / gs²)

where i is the current iteration, and gs is length of one axis.

With a bit of extrapolation, here's a formula2 for an nD grid: cn = floor(i / gsn-1) % gs
For example:

x = floor( i / gs⁰ ) % gs    # 1D
y = floor( i / gs¹ ) % gs    # 2D 
z = floor( i / gs² ) % gs    # 3D 
a = floor( i / gs³ ) % gs    # 4D

etc.

NOTE:

  1. The x value can be simplified to i % gs because
    i/gs0 % gs => i/1 % gs => i % gs. Likewise, we can remove the % gs from the calculation of the z value, because the loop should never go over gs3
  2. This formula only works for cubic grids (ie. grids whose axes all have the same number of points on them - 2x2x2x2, 5x5x5, etc.). 3x4x5 grids, for example, require a different formula.
user_55342320

x ticks up the fastest, incrementing by 1 every time i increments, and wraps around when it reaches gridsize:

x = i % gridsize

y ticks up more slowly, incrementing by 1 every time i increases by gridsize, but also wraps around when it reaches gridsize:

y = (i // gridsize) % gridsize

z ticks up the slowest, incrementing by 1 every time i increases by gridsize**2, and we don't need it to wrap around:

z = i // gridsize**2

We can generalize this:

x = (i // gridsize**0) % gridsize
y = (i // gridsize**1) % gridsize
z = (i // gridsize**2) % gridsize

I'm sure you see the pattern here.

user_146370

I wouldn't use a formula but just this:

r = range(gridsize)
grid = [Node(x, y, z) for z in r for y in r for x in r]

Or with an arbitrary dimension, using itertools.product:

grid = [Node(*p[::-1]) for p in product(range(gridsize), repeat=griddim)]

If you don't mind the order of the nodes, you can leave out the [::-1] or also use itertools.starmap:

grid = list(starmap(Node, product(range(gridsize), repeat=griddim)))
user_126710570
Related