Generazione coordinate triangolari / esagonali (xyz)

Question

Sto cercando di trovare una funzione iterativa che genera coordinate xyz una griglia esagonale. Con una posizione di partenza esagono (0,0,0 dire per semplicità), voglio calcolare le coordinate di ciascun "anello" successivi di esagoni, come illustrato qui:

Finora, tutto quello che sono riuscito a venire in mente è questo (ad esempio in 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);
        }
    }
}

So ogni anello contiene più di sei punti rispetto al precedente ed ogni 120 ° vettore contiene un punto addizionale per ogni passo dal centro. So anche che x + y + z = 0 per tutte le tessere. Ma come faccio a generare un elenco di coordinate che seguono la sequenza di seguito?

    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

Un'altra possibile soluzione, che viene eseguito in O (raggio ² ), a differenza del O (raggio ⁴ ) di soluzione di tehMick (a scapito di un sacco di stile) è questa:

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 scritta un po 'più conciso:

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

E 'ispirato dal fatto gli esagoni sono in realtà sulla parte esterna di un esagono se stessi, in modo da poter trovare le coordinate di uno dei suoi punti, e quindi calcolare gli altri spostando sui suoi bordi 6.

Answer 2

Non solo è x + y + z = 0, ma i valori assoluti di x, y, z sono uguali al doppio del raggio dell'anello. Questo dovrebbe essere sufficiente per identificare ogni esagono in ogni anello successivo:

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

Questo è stato un divertente puzzle.

O (raggio ² ) , ma con (si spera) un po 'più stile di la soluzione di Ofri. mi venne in mente che le coordinate potrebbero essere generati come se si stesse 'camminare' intorno al ring con una direzione (mossa) vettore, e che una volta era equivalente a spostare lo zero in tutto il vettore di movimento .

Questa versione ha anche il vantaggio rispetto soluzione di Eric in quanto non tocca mai su coordinate non valide (Eric li respinge, ma questo non ha mai nemmeno per testarli).

# 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

Tre urrà per affettare sequenza di Python.

Answer 4

Ok, dopo aver provato entrambe le opzioni che ho optato per la soluzione di Ofri in quanto è un pochino più veloce e ha reso facile per fornire un valore di offset iniziale. Il mio codice ora assomiglia a questo:

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

Il metodo "placeTile" utilizza cloneNode per copiare un elemento SVG predefinita e ci vogliono circa 0,5 ms per tegola per l'esecuzione che è più che sufficiente. Un grande grazie a tehMick e Ofri per il vostro aiuto!

JS