Генерация треугольных/гексагональных координат (xyz)

Я пытаюсь создать итеративную функцию, которая генерирует координаты xyz для гексагональной сетки. Математика никогда не была легкой для меня (я просто не очень умна!), И эта проблема меня сильно озадачила. С начальным шестнадцатеричным положением (скажем, 0,0,0 для упрощения) я хочу рассчитать координаты для каждого последующего "кольца" шестиугольников, как показано здесь:

До сих пор все, что мне удалось найти, это (пример в 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);
        }
    }
}

Я знаю, что каждое кольцо содержит еще шесть точек, чем предыдущее, и каждый 120 & deg; вектор содержит одну дополнительную точку для каждого шага от центра. Я также знаю, что x + y + z всегда = 0. Но как я могу сгенерировать список координат, следующих за этой последовательностью:

    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

Я, вероятно, смущен простотой ответа, но, пожалуйста, не позволяйте этому мешать вам вносить свой вклад!;) Как я уже сказал, я просто не очень умный!

Большое спасибо,

Ответ 1

Другое возможное решение, которое работает в O (радиус ^ 2), в отличие от O (радиус ^ 4) решения tehMick (за счет большого количества стилей), таково:

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

или написано немного более кратко:

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

Его вдохновляет тот факт, что шестиугольники фактически находятся снаружи самого шестиугольника, поэтому вы можете найти координаты 1 его точек, а затем вычислить остальные, переместив их на 6 ребер.

Ответ 2

Не только x + y + z = 0, но абсолютные значения x, y и z равны удвоенному радиусу кольца. Этого должно быть достаточно, чтобы идентифицировать каждый шестиугольник на каждом последующем кольце:

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

Вывод: 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

Ответ 3

Это была забавная головоломка.

O (радиус ^ 2), но с (надеюсь) немного больше стиля, чем решение Ofri. Мне пришло в голову, что координаты могут быть сгенерированы так, как будто вы "гуляете" по кольцу с помощью вектора направления (перемещения), и что поворот был эквивалентен смещению нуля вокруг вектора перемещения.

Эта версия также имеет преимущество над решением Эрика в том, что она никогда не затрагивает недействительные координаты (Эрик отвергает их, но это никогда не нужно проверять).

# 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

Три ура для нарезки последовательности python.

Ответ 4

Хорошо, попробовав оба параметра, которые я установил на решение Ofri, поскольку он немного быстрее и облегчил предоставление начального значения смещения. Теперь мой код выглядит следующим образом:

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

Метод "placeTile" использует cloneNode для копирования предопределенного элемента svg и для выполнения занимает около 0,5 мс на каждый фрагмент, что более чем достаточно. Большое спасибо tehMick и Ofri за вашу помощь!