Generazione di coordinate triangolari/esagonali (xyz)

Question

Sto provando a creare una funzione iterativa che genera le coordinate xyz per una griglia esagonale. La matematica non è mai stata facile per me (non sono molto intelligente!) E questo problema mi ha bloccato. Con una posizione di partenza esagonale (0,0,0 dire per simplicty) voglio calcolare le coordinate di ogni "anello" successivi di esagoni, come illustrato qui:

Finora, tutto quello che ho riuscito a venire con questo (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 sempre = 0. Ma come faccio a generare un elenco di coordinate che seguono questa sequenza:

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 

Sono probabilmente andando a essere imbarazzato dalla semplicità della risposta ma per favore non lasciare che questo ti impedisca di contribuire! ;) Come ho detto, non sono molto intelligente!

Grazie,

JS

Answer 1

Un'altra possibile soluzione, che viene eseguito in O (raggio^2), a differenza della O (raggio^4) della soluzione di tehMick (a scapito di un sacco di stile) è questo:

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

la sua ispirazione dal fatto gli esagoni sono in realtà sulla parte esterna della esagono se stessi, in modo da poter trovare le coordinate di uno dei suoi punti, e poi calcola gli altri spostandoti sui suoi 6 lati.

Answer 2

Non solo è x + i valori assoluti di x y + z = 0, ma, Y e Z sono pari 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) 
       document.body.innerHTML += (j + "," + k + "," + l + "<br />"); 
     document.body.innerHTML += ("<br />"); 
    } 

uscita: 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, dopo aver provato entrambe le opzioni, ho optato per la soluzione di Ofri poiché è leggermente più veloce e ha reso facile 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 tuo aiuto!

JS

Answer 4

Questo è stato un divertente puzzle.

O (raggio^2) ma con (si spera) un po 'più di stile rispetto alla soluzione di Ofri. Mi è venuto in mente che le coordinate potrebbero essere generate come se stessimo "camminando" intorno all'anello usando un vettore di direzione (spostamento) e che una svolta equivalesse a spostare lo zero attorno al vettore di movimento.

Questa versione ha anche il vantaggio sulla soluzione di Eric in quanto non tocca mai le coordinate non valide (Eric le rifiuta, ma questo non ha nemmeno bisogno di testarle).

# 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 applausi per affettare la sequenza di Python.