Generación de coordenadas hexagonales / triangulares (XYZ)

Question

Estoy tratando de llegar a una función iterativa que genera coordenadas XYZ para una rejilla hexagonal. Con una posición de partida hexagonal (0,0,0 decir por simplicidad), quiero calcular las coordenadas de cada "anillo" sucesiva de hexágonos, como se ilustra a continuación:

Hasta ahora, todo lo que he conseguido llegar a decir esto (ejemplo en javascript):

var radius = 3
var xyz = [0,0,0];

// for each ring
for (var i = 0; i < radius; i++) {
    var tpRing = i*6;
    var tpVect = tpRing/3;
    // for each vector of ring
    for (var j = 0; j < 3; j++) {
        // for each tile in vector
        for(var k = 0; k < tpVect; k++) {
            xyz[0] = ???;
            xyz[1] = ???;
            xyz[2] = ???;
            console.log(xyz);
        }
    }
}

Sé que cada anillo contiene seis puntos más que el anterior y cada 120 ° vector contiene un punto adicional para cada paso del centro. También sé que x + y + z = 0 para todos los azulejos. Pero, ¿cómo puedo generar una lista de coordenadas que siguen la secuencia de abajo?

    0, 0, 0

    0,-1, 1
    1,-1, 0
    1, 0,-1
    0, 1,-1
   -1, 1, 0
   -1, 0, 1

    0,-2, 2
    1,-2, 1
    2,-2, 0
    2,-1,-1
    2, 0,-2
    1, 1,-2
    0, 2,-2
   -1, 2,-1
   -2, 2, 0
   -2, 1, 1
   -2, 0, 2
   -1,-1, 2

Answer 1

Otra posible solución, que se ejecuta en O (radio ² ), a diferencia de la O (radio ⁴ ) de solución de tehMick (a expensas de un montón de estilo) es la siguiente:

radius = 4
for r in range(radius):
    print "radius %d" % r
    x = 0
    y = -r
    z = +r
    print x,y,z
    for i in range(r):
        x = x+1
        z = z-1
        print x,y,z
    for i in range(r):
        y = y+1
        z = z-1
        print x,y,z
    for i in range(r):
        x = x-1
        y = y+1
        print x,y,z
    for i in range(r):
        x = x-1
        z = z+1
        print x,y,z
    for i in range(r):
        y = y-1
        z = z+1
        print x,y,z
    for i in range(r-1):
        x = x+1
        y = y-1
        print x,y,z

o escrita un poco más concisa:

radius = 4
deltas = [[1,0,-1],[0,1,-1],[-1,1,0],[-1,0,1],[0,-1,1],[1,-1,0]]
for r in range(radius):
    print "radius %d" % r
    x = 0
    y = -r
    z = +r
    print x,y,z
    for j in range(6):
        if j==5:
            num_of_hexas_in_edge = r-1
        else:
            num_of_hexas_in_edge = r
        for i in range(num_of_hexas_in_edge):
            x = x+deltas[j][0]
            y = y+deltas[j][1]
            z = z+deltas[j][2]            
            print x,y,z

Está inspirado por el hecho de los hexágonos están realmente en el exterior de un hexágono a sí mismos, para que pueda encontrar las coordenadas de 1 de sus puntos, y luego calcular los demás moviendo en sus bordes 6.

Answer 2

No sólo es x + y + z = 0, pero los valores absolutos de x, y y z son iguales a dos veces el radio del anillo. Esto debería ser suficiente para identificar cada hexágono en cada anillo sucesivo:

var radius = 4;
for(var i = 0; i < radius; i++)
{
    for(var j = -i; j <= i; j++)
    for(var k = -i; k <= i; k++)
    for(var l = -i; l <= i; l++)
        if(Math.abs(j) + Math.abs(k) + Math.abs(l) == i*2 && j + k + l == 0)
            console.log(j + "," + k + "," + l);
    console.log("");
}

Answer 3

Este fue un divertido puzzle.

O (radio ² ) pero con (esperemos) un poco más estilo que solución de Ofri. se me ocurrió que las coordenadas se podrían generar como si estuviera 'caminando' alrededor del anillo usando un vector (mover) la dirección, y que a su vez era un equivalente a desplazar el cero alrededor del vector de movimiento .

Esta versión también tiene la ventaja sobre href="https://stackoverflow.com/a/2049274/241211"> solución de Eric en que nunca toca en coordenadas no válidas (Eric de las rechaza, pero éste ni siquiera tiene que probarlos).

# enumerate coords in rings 1..n-1; this doesn't work for the origin
for ring in range(1,4):
    # start in the upper right corner ...
    (x,y,z) = (0,-ring,ring)
    # ... moving clockwise (south-east, or +x,-z)
    move = [1,0,-1]         

    # each ring has six more coordinates than the last
    for i in range(6*ring):
        # print first to get the starting hex for this ring
        print "%d/%d: (%d,%d,%d) " % (ring,i,x,y,z)
        # then move to the next hex
        (x,y,z) = map(sum, zip((x,y,z), move))

        # when a coordinate has a zero in it, we're in a corner of
        # the ring, so we need to turn right
        if 0 in (x,y,z):
            # left shift the zero through the move vector for a
            # right turn
            i = move.index(0)
            (move[i-1],move[i]) = (move[i],move[i-1])

    print # blank line between rings

Tres hurras por la secuencia de corte en rodajas de Python.

Answer 4

Ok, después de probar las dos opciones me he decidido por la solución de Ofri ya que es un poquito más rápido y hace que sea fácil para proporcionar un valor de desplazamiento inicial. Mi código ahora se ve así:

var xyz = [-2,2,0];
var radius = 16;
var deltas = [[1,0,-1],[0,1,-1],[-1,1,0],[-1,0,1],[0,-1,1],[1,-1,0]];
for(var i = 0; i < radius; i++) {
        var x = xyz[0];
        var y = xyz[1]-i;
        var z = xyz[2]+i;
        for(var j = 0; j < 6; j++) {
                for(var k = 0; k < i; k++) {
                        x = x+deltas[j][0]
                        y = y+deltas[j][1]
                        z = z+deltas[j][2]
                        placeTile([x,y,z]);
                }
        }
}

El método "placeTile" utiliza cloneNode copiar un elemento SVG predefinido y se tarda aproximadamente 0,5 ms por azulejo para ejecutar el cual es más que suficiente. Muchas gracias a tehMick y Ofri por su ayuda!

JS