Spacehug Spacehug - 3 years ago 37
Python Question

Hexagonal filling of 2D array

I am trying to fill an array with unique integers (except for 0) in such a fashion:

# range(0, 37)
[[ 0, 0, 0, 36, 19, 20, 21],
[ 0, 0, 35, 18, 7, 8, 22],
[ 0, 34, 17, 6, 1, 9, 23],
[33, 16, 5, 0, 2, 10, 24],
[32, 15, 4, 3, 11, 25, 0],
[31, 14, 13, 12, 26, 0, 0],
[30, 29, 28, 27, 0, 0, 0]]


(This represents hex grid as 2D array)

How to figure out the size of 2D array (width and height) before it is filled?
How to determine the coordinate at which the next integer should be placed?

Thanks to @Błotosmętek I am now able to figure out the size of the array:

def array_size(n):
k = 0
while n > 0:
k += 1
n -= 6 * k
return 2 * k + 1

Answer Source

Answering my own question:

To figure out how to place values in given manner, we need to figure out coordinates delta for each item.

For the sake of explanation, I will use n = 60 elements.

To do that, we need to know the size of the array we will get, this can be accomplished by what @Błotosmętek suggested:

def array_size(n):
k = 0
while n > 0:
    k += 1
    n -= 6 * k
return 2 * k + 1

array_size = array_size(n)

(By the way, thanks for great heads-up.) Now, we need the coordinates for array center, which is pretty easy:

# This is (4, 4), the exact coordinates we need for said amount of items (60)
array_center = (array_size // 2, array_size // 2)

Next, we get the deltas. I am not sure that this is the best way to do so, but anyway:

def get_coordinates_delta(n):
    x = [0]
    x_ones = 1
    x_zeroes = 1
    while len(x) <= n:
        x += ([1] * x_ones + [0] * x_zeroes + [-1] * (x_ones + 1) + [0] * x_zeroes)
        x_ones += 2
        x_zeroes += 1

    y = [0, -1]
    y_ones = 2
    y_zeroes = 1
    while len(y) <= n:
        y += ([1] * y_ones + [0] * y_zeroes + [-1] * (y_ones + 1) + [0] * y_zeroes)
        y_ones += 2
        y_zeroes += 1
    return [x for x in zip(x[:n], y[:n])]

coordinates_delta = get_coordinates_delta(n)

And now the fun part, we place everything we have onto the grid:

def fill_matrix():
    matrix = [[0] * array_size for _ in range(array_size)]
    x, y = array_center
    for item, (dx, dy) in zip(range(n), coordinates_delta):
        x += dx
        y += dy
        matrix[y][x] = item
    return matrix

matrix = fill_matrix()    

Voila,

for line in matrix:
    print(line)

gives us this:

[ 0,  0,  0,  0,  0, 37, 38, 39, 40]
[ 0,  0,  0, 59, 36, 19, 20, 21, 41]
[ 0,  0, 58, 35, 18,  7,  8, 22, 42]
[ 0, 57, 34, 17,  6,  1,  9, 23, 43]
[56, 33, 16,  5,  0,  2, 10, 24, 44]
[55, 32, 15,  4,  3, 11, 25, 45,  0]
[54, 31, 14, 13, 12, 26, 46,  0,  0]
[53, 30, 29, 28, 27, 47,  0,  0,  0]
[52, 51, 50, 49, 48,  0,  0,  0,  0]
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download