Gerando coordenadas triangulares/hexagonais (XYZ)

Question

Estou tentando criar uma função iterativa que gera coordenadas XYZ para uma grade hexagonal. Com uma posição hexadecimal inicial (digamos 0,0,0 por simplicidade), quero calcular as coordenadas para cada "anel" sucessivo de hexágonos, como ilustrado aqui:

Até agora, tudo o que consegui criar é este (exemplo em 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);
        }
    }
}

Eu sei que cada anel contém mais seis pontos do que o anterior e cada vetor de 120 ° contém um ponto adicional para cada etapa do centro. Eu também sei disso x + y + z = 0 Para todos os ladrilhos. Mas como posso gerar uma lista de coordenadas que seguem a sequência abaixo?

    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

Outra solução possível, que corre em O (raio²), ao contrário do O (raio⁴) do Solução de Tehmick (À custa de muito estilo) é o seguinte:

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

ou escrito um pouco mais 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

É inspirado pelo fato de os hexágonos estarem no exterior de um hexágono, para que você possa encontrar as coordenadas de 1 de seus pontos e depois calcular os outros movendo -se em suas 6 arestas.

Answer 2

Não apenas é x + y + z = 0, mas os valores absolutos de x, y e z são iguais a duas vezes o raio do anel. Isso deve ser suficiente para identificar cada hexágono em cada anel sucessivo:

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 foi um quebra -cabeça divertido.

O (raio²) mas com (espero) um pouco mais de estilo do que Solução de Ofri. Ocorreu -me que as coordenadas poderiam ser geradas como se você estivesse "andando" ao redor do anel usando um vetor de direção (mover), e que uma curva era equivalente a mudar o zero em torno do vetor de movimentação.

Esta versão também tem a vantagem sobre Solução de Eric na medida em que nunca toca em coordenadas inválidas (Eric as rejeita, mas essa nunca precisa testá -las).

# 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

Três aplausos pelo fatiamento da sequência de Python.

Answer 4

OK, depois de experimentar as duas opções, eu resolvi a solução de Ofri, pois é um pouco mais rápido e facilitou o fornecimento de um valor de deslocamento inicial. Meu código agora se parece com o seguinte:

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]);
                }
        }
}

O método "placetile" usa o CLONENODE para copiar um elemento SVG predefinido e leva aproximadamente 0,5ms por ladrilho para executar o que é mais do que bom o suficiente. Um grande obrigado a Tehmick e Ofri por sua ajuda!

JS