A reader asked about converting q,r coordinates for a hex into *indices into a 1d array*. In the hexagon guide I recommend using a hash table for small grids, and using an array of arrays for larger grids. But an array of arrays can often be condensed into a 1d array, if you can calculate the indices. I've calculated indices for a rectangular map before but I haven't done one for hexagonal maps. My initial thought was to use spirals but I think there's more straightforward way. After I wrote this page, Sander Evers pointed to a more clever and much simpler solution^{[1]}.

The top and bottom halves of a hexagonal map are *trapezoids*. That means we can calculate the sizes of each row. And we can also calculate the *cumulative sum* of those sizes, by using the formula for the area of a trapezoid. The cumulative sum gives us a function from `r` to `index`.

*I'm going to assume this hexagonal map is centered at 0,0* and also assume that it's *pointy top orientation*. For a flat top orientation, you'll have to work out the math with rows and columns swapped.

The `index` of a `hex(q, r)` is the (`start index` of row `r`) plus (`q` minus the `first column`).

The `first column` of row `r` is `max(0, MAPSIZE - r)`. (Note: MAPSIZE here is the "radius", 5 in the above diagram, not the "diameter".)

The `row size` is `1 + 2 * MAPSIZE - abs(r)`.

The `start index` is *cumulative sum* of the `row size` of each row above it. In theory we can calculate it by adding the previous row's row size and the previous row's start index. However, we want a closed formula for this, so we instead use the area of a trapezoid: `(first row size + last row size) / 2 * num rows`.

But there are two trapezoids, so to calculate the `start index` we need to know whether we're in the upper or lower trapezoid. Here's the code:

let firstRow = -MAPSIZE if (r <= 0) { let j = r - firstRow return areaOfTrapezoid(MAPSIZE + 1, MAPSIZE + j, j) } else { const areaOfUpperTrapezoid = areaOfTrapezoid(MAPSIZE + 1, 1 + MAPSIZE * 2, MAPSIZE + 1) let j = r - 1 return areaOfUpperTrapezoid + areaOfTrapezoid(MAPSIZE * 2, MAPSIZE * 2 - j + 1, j) }

And we need a helper function

function areaOfTrapezoid(first, last, rows) { return (first + last) / 2 * rows; }

In the diagram above I've displayed the calculated start index.

**But this is for the forwards direction**, from a hex to an index. We might also want the backwards direction, from an index to a hex. We need to invert the area of a trapezoid formula. It's a quadratic polynomial, representing a parabola. To invert it we need to solve the polynomial using the quadratic formula.

*It was a great surprise to me to see the quadratic formula show up here*.

Let's start with the upper trapezoid:

function areaOfTrapezoid(first, last, rows) { return (first + last) / 2 * rows; } let firstRow = -MAPSIZE; let j = r - firstRow let index = areaOfTrapezoid(MAPSIZE + 1, MAPSIZE + j, j)

Let's expand out the formula by inlining the `areaOfTrapezoid`

function:

let firstRow = -MAPSIZE; let j = r - firstRow let index = (MAPSIZE + 1 + MAPSIZE + j) / 2 * j

and we can inline `j`:

let firstRow = -MAPSIZE; let index = (MAPSIZE + 1 + MAPSIZE + r - firstRow) / 2 * (r - firstRow)

and then inline `firstRow`:

let index = (MAPSIZE + 1 + MAPSIZE + r + MAPSIZE) / 2 * (r + MAPSIZE)

and simplify:

let index = (3 * MAPSIZE + 1 + r) / 2 * (r + MAPSIZE)

Then multiply out using the distributive rule:

let index = (3 * MAPSIZE * r + r + r * r + 3 * MAPSIZE * MAPSIZE + MAPSIZE + r * MAPSIZE) / 2

Note: when I do this kind of thing I'll calculate the value with each version of the expression, to make sure they give me the same result. If they don't that tells me one of my rewrite steps has a bug, and also tells me *which* rewrite step is incorrect. And I *did* catch bugs in the above rewrites. That's why I like to make code transformations with many small steps.

Finally we group the terms based on whether they're for r², r, or 1:

let index = 1/2 * r * r + (2 * MAPSIZE + 1/2) * r + (3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE)

Now we have a *polynomial* in terms of `r`, and we can solve for it using the quadratic formula. We have to rewrite one more time to use the quadratic formula:

0 = 1/2 * r * r + (2 * MAPSIZE + 1/2) * r + (3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index)

This matches the quadratic formula pattern `a * r² + b * r + c = 0`, with:

a = 1/2 b = 2 * MAPSIZE + 1/2 c = 3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index

So we can apply the quadratic formula, `r = (-b ± sqrt(b*b - 4*a*c)) / (2 * a)`:

function rowFromIndex(index) { let a = 1/2 let b = 2 * MAPSIZE + 1/2 let c = 3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index let r = (-b + Math.sqrt(b*b - 4*a*c)) / (2 * a) return r }

It looks like the + variant is what we want, so I don't calculate the - variant. Does this work? Well, I tried it with a test program and it seems to work!

So if you have an index:

function firstColumn(r) { return -MAPSIZE - Math.min(r, 0) } function startIndexOfRow(r) { if (r <= 0) { // upper trapezoid return (3 * MAPSIZE + 1 + r) / 2 * (r + MAPSIZE) } else { // lower trapezoid return (3 * MAPSIZE + 2) / 2 * (MAPSIZE + 1) + (4 * MAPSIZE + 2 - r) / 2 * (r - 1) } } function hexFromIndex(index) { let r = Math.floor(rowFromIndex(index)) let q = (index - startIndexOfRow(r)) + firstColumn(r) return [q, r] }

**This is only for the upper trapezoid**. I need to do something similar for the lower trapezoid. I didn't show all the work here but it's in the test program.

a = -1/2 b = 2 * MAPSIZE + 3/2 c = 3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index

So we can apply the quadratic formula, `r = (-b ± sqrt(b*b - 4*a*c)) / (2 * a)`:

function rowFromIndex(index) { let a = -1/2 let b = 2 * MAPSIZE + 3/2 let c = 3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index let r = (-b + Math.sqrt(b*b - 4*a*c)) / (2 * a) return r }

It looks like here too I want the + variant and not the - variant, although it's less obvious to me why. Do I need to worry about numerical stability? See this post^{[3]} ; I think neither condition applies here. To avoid further numerical issues I can multiply the whole equation by 2, so that `a`, `b`, and `c` are all integers.

Putting everything together, I need to figure out *which* trapezoid I'm in, and then use the corresponding formula:

function rowFromIndex(index) { let crossoverIndex = (3/2 * MAPSIZE + 1) * (1 + MAPSIZE) if (index < crossoverIndex) { // Upper trapezoid let a = 1 let b = 4 * MAPSIZE + 1 let c = 3 * MAPSIZE * MAPSIZE + MAPSIZE - 2 * index let r = (-b + Math.sqrt(b*b - 4*a*c)) / (2 * a) return r } else { // Lower trapezoid let a = -1 let b = 4 * MAPSIZE + 3 let c = 3 * MAPSIZE * MAPSIZE + MAPSIZE - 2 * index let r = (-b + Math.sqrt(b*b - 4*a*c)) / (2 * a) return r } }

That's just the row. To get the hex:

function hexFromIndex(index) { let r = Math.floor(rowFromIndex(index)) let q = (index - startIndexOfRow(r)) + firstColumn(r) return [q, r] }

This was a fun afternoon puzzle to figure out.

Note: I might still have to worry about floating point precision, as `floor()` on 1.99999999999 is going to give a very different from from 2.0000000000. But as we're working with integers, I'm *hoping* it's not a problem. Hope is no guarantee though. So let's think through this a bit more. What is the worst that `rowFromIndex` could return? The indices are roughly evenly spaced per row, and `rowFromIndex` increases by +1 per row. The worst case will be the last column on the widest row, which will be `1/(2*MAPSIZE+1)` away from an integer. The quadratic formula is using `MAPSIZE*MAPSIZE` in its calculations. When that squared difference is less than 10^{-16} (around `DBL_EPSILON`

) we're in trouble, but that won't happen until the MAPSIZE is around 10^{8}, so I think we're ok. Experimentally, I started noticing issues around MAPSIZE somewhere between 10^{7} and 10^{8}. I'm no expert on floating point math though.

Source code: the diagram and standalone test program.