Generating triangular/hexagonal coordinates (xyz)

Question

I'm trying to come up with an iterative function that generates xyz coordinates for a hexagonal grid. With a starting hex position (say 0,0,0 for simplicity), I want to calculate the coordinates for each successive "ring" of hexagons, as illustrated here:

So far, all I've managed to come up with is this (example 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);
        }
    }
}

I know each ring contains six more points than the previous and each 120° vector contains one additional point for each step from the center. I also know that x + y + z = 0 for all tiles. But how can I generate a list of coordinates that follow the sequence below?

    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

Alkane

Small correction. Every ring contains 6*k points, or 6*(k-1) more points than previous one, where k is the ring index that is started from zero. – Tolan

Answer 1

Another possible solution, that runs in O(radius²), unlike the O(radius⁴) of tehMick's solution (at the expense of a lot of style) is this:

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

or written a little more concisely:

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

It's inspired by the fact the hexagons are actually on the exterior of a hexagon themselves, so you can find the coordinates of 1 of its points, and then calculate the others by moving on its 6 edges.

Cairngorm

This is an interesting solution as well, thank you! I have actually implemented both methods in my project with the ability to switch between them and am currently running some benchmarks to see which is the faster. Another factor is how easy it will be to change the "start" position from 0,0,0 to another point on the grid (say 5,-3,-2) and generate the grid around that point. Any ideas on this? – Alkane

Very simple: in the first x=0, y=-r, z=+r lines, just add the starting pos, like: x=x0, y=y0-r, z=z0+r, and you're done :) – Cairngorm

In the end, this is my accepted answer as it is a tiny bit faster and easier to feed an offset starting position. See my answer below for final implementation. Thanks Ofri! – Alkane

Answer 2

Not only is x + y + z = 0, but the absolute values of x, y and z are equal to twice the radius of the ring. This should be sufficient to identify every hexagon on each successive ring:

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

Spindling

Wow, that is incredibly simple! I've been staring at the sequence trying to find just such a relationship but not knowing much of geometry maths it's just given me a headache. Thanks to your example I now see the relationship (looking at the Wikipedia article on absolute values further helped the penny drop). I will give this a whirl but it already looks like a accepted answer. Thanks! – Alkane

I suppose this method can be used even if the starting point is not 0,0,0? How would I feed in the start coordinates? - actually, never mind that, think I know how to do this. Will post full solution when done. – Alkane

Yup, as you probably guessed, just start i at the radius of the innermost ring you would like to output. – Spindling

I implemented this last night and it works brilliantly, thank you! I couldn't, however, figure out a way to offset the start position from 0,0,0 to, say, 5,-3,-2 and draw the grid around that point. Any suggestions? – Alkane

You could always just offset your output. – Spindling

I would have liked to select both these answers as the "accepted answer" but of course I can't. +1 for your kind help though! – Alkane

Answer 3

This was a fun puzzle.

O(radius²) but with (hopefully) a bit more style than Ofri's solution. It occurred to me that coordinates could be generated as though you were "walking" around the ring using a direction (move) vector, and that a turn was equivalent to shifting the zero around the move vector.

This version also has the advantage over Eric's solution in that it never touches on invalid coordinates (Eric's rejects them, but this one never even has to test them).

# 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

Three cheers for python's sequence slicing.

Paleontography

Answer 4

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
ctx.textAlign = "center";

const radius = 20;
const altitude = Math.sqrt(3) * radius;
const total = 3;
for (let x = -total; x <= total; x++) {
    let y1 = Math.max(-total, -x-total);
    let y2 = Math.min(total, -x+total);
    for (let y = y1; y <= y2; y++) {
        let xx = x * altitude + Math.cos(1/3*Math.PI) * y * altitude;
        let yy = y * radius * 1.5;
        xx += canvas.width/2;
        yy += canvas.height/2;
        drawHex(xx, yy, radius);
        ctx.fillText(x+","+y, xx, yy);
    }
}

function drawHex(x, y, radius){
    ctx.beginPath();
    for(let a = 0; a < Math.PI*2; a+=Math.PI/3){
        let xx = Math.sin(a) * radius + x;
        let yy = Math.cos(a) * radius + y;
        if(a == 0) ctx.moveTo(xx, yy);
        else ctx.lineTo(xx, yy);
    }
    ctx.stroke();
}

<canvas id="canvas" width=250 height=250>

Laudatory

Answer 5

After trying both the options, I've settled on Ofri's solution as it is a tiny bit faster and made it easy to provide an initial offset value. My code now looks like this:

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

The placeTile method uses cloneNode to copy a predefined SVG element, and it takes approx 0.5ms per tile to execute which is more than good enough. A big thanks to tehMick and Ofri for your help!

Alkane

this doesn't work for radius = 1. you are missing a placeTile([x,y,z]); just before the second for-loop. – Hinckley