Generando coordenadas triangulares/hexagonales (xyz)

Question

Estoy tratando de encontrar una función iterativa que genere coordenadas xyz para una cuadrícula hexagonal. Las matemáticas nunca han sido fáciles para mí (¡no soy muy inteligente!) Y este problema me ha dejado perplejo. Con una posición de partida hexagonal (0,0,0 decir para simplicty) Quiero calcular las coordenadas de cada "anillo" sucesiva de hexágonos, como se ilustra aquí:

Hasta ahora, todo lo que he logrado llegar a es este (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é 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. Pero siempre cómo puedo generar una lista de coordenadas que siguen esta secuencia:

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 

Probablemente voy a ser avergonzado por la simplicidad de la respuesta, pero por favor, ¡no dejes que eso te impida contribuir! ;) Como digo, ¡simplemente no soy muy inteligente!

Muchas gracias,

JS

Answer 1

Otra solución posible, que se ejecuta en O (radio^2), a diferencia del O (radio^4) de la solución de tehMick (a costa de mucho estilo) es esto:

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 escribir 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 

su inspirados por el hecho de los hexágonos son en realidad en el exterior del hexágono sí mismos, para que pueda encontrar las coordenadas de 1 de sus puntos, y luego calcule los otros moviendo sus 6 bordes.

Answer 2

No sólo es X + los valores absolutos de x y + z = 0, pero, 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) 
       document.body.innerHTML += (j + "," + k + "," + l + "<br />"); 
     document.body.innerHTML += ("<br />"); 
    } 

de salida: 0,0,0

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

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

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

Answer 3

Ok, después de probar ambas opciones, me he decidido por la solución de Ofri, ya que es un poco más rápida y hace que sea más fácil proporcionar un valor de compensación 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 tu ayuda!

JS

Answer 4

Este fue un rompecabezas divertido.

O (radio^2) pero con (con suerte) un poco más de estilo que la solución de Ofri. Se me ocurrió que se podían generar coordenadas como si estuvieras "caminando" alrededor del anillo usando un vector de dirección (movimiento), y que un giro equivalía a desplazar el cero alrededor del vector de movimiento.

Esta versión también tiene la ventaja sobre la solución de Eric en que nunca toca coordenadas inválidas (Eric las rechaza, pero esta nunca tiene que probarlas).

# 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 para cortar en secuencia python.