Generowanie współrzędnych trójkątnych/heksagonalnych (xyz)

Question

Próbuję wymyślić funkcję iteracyjną, która generuje współrzędne xyz dla siatki sześciokątnej. Matematyka nigdy nie była dla mnie łatwa (jestem po prostu niezbyt mądra!) I ten problem mnie zaskoczył. Z pozycji wyjściowej hex (powiedzmy 0,0,0 dla simplicty) Chcę obliczyć współrzędne dla każdego kolejnego „pierścień” sześciokątów, jak pokazano tutaj:

Jak dotąd, wszystko mam udało się wymyślić jest to (przykład w 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); 
     } 
    } 
} 

znam każdy pierścień zawiera sześć więcej punktów niż poprzedni i każde 120 ° wektor zawiera jeden dodatkowy punkt za każdym kroku od centrum miasta. Wiem też, że x + y + z = 0. Ale zawsze jak mogę wygenerować listę współrzędnych, które następują tę sekwencję:

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 

Jestem prawdopodobnie będzie zakłopotany przez prostotę, ale proszę o odpowiedź nie pozwól, aby cię to powstrzymało! ;) Tak jak mówię, po prostu nie jestem sprytny!

Dzięki wielu,

JS

Answer 1

Innym możliwym rozwiązaniem, które działa w O (promień^2), w przeciwieństwie do O (promień^4) rozwiązania TehMick'a (kosztem wielu stylów) jest:

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 

lub napisany trochę bardziej zwięźle:

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 

Its inspirowane rzeczywistości sześciokąty są faktycznie na zewnątrz sześciokąt siebie, dzięki czemu można znaleźć współrzędne 1 z jego punktów, a następnie obliczyć pozostałe, poruszając się po swoich 6 krawędziach.

Answer 2

nie tylko suma x + y + z = 0, ale bezwzględne wartości x, y i z równa się dwukrotności promienia pierścienia.To powinno być wystarczające do identyfikacji każdego sześciokąta w każdym kolejnym pierścieniem:

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 />"); 
    } 

wyjściowa: 0,0,0

-1,0,1 -1,1,0 0 -1 1 0,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,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, po wypróbowaniu obu opcji zdecydowałem się na rozwiązanie Ofri, ponieważ jest ono trochę szybsze i ułatwiło podanie początkowej wartości przesunięcia. Mój kod wygląda teraz tak:

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

W „placeTile” metoda wykorzystuje cloneNode skopiować predefiniowany element SVG i trwa ok 0,5ms dachówki wykonać co jest więcej niż wystarczająco dobre. Wielkie podziękowania dla TehMick i Ofri za pomoc!

JS

Answer 4

To była zabawna zagadka.

O (promień^2), ale z (miejmy nadzieję) nieco bardziej stylem niż rozwiązanie Ofri. Przyszło mi do głowy, że współrzędne mogą być generowane tak, jakbyś "krążył" wokół pierścienia za pomocą wektora kierunku (ruchu), i że skręt był równoważny przesunięciu zera wokół wektora ruchu.

Ta wersja ma również przewagę nad rozwiązaniem Erica, ponieważ nigdy nie dotyka nieważnych współrzędnych (Eric odrzuca je, ale ten nie musi nawet ich testować).

# 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 

Trzy okrzyki za krojenie sekwencji Pythona.