# More pixel to hex approaches

from Red Blob Games
31 Jan 2015

There are several different ways to convert a pixel location into a hex coordinate. On the main page I cover what I consider to be the simplest approach, reusing the `hex_round()` function that we already used in line drawing. But there are many other approaches that I’ve found or that readers have sent to me. Some are faster. Some are more flexible. Some handle edge cases better. I’m collecting them on this page.

## 1  Tested algorithms#

These are the algorithms I’ve tested myself, with code on this page, and the output of running that code. All of these tests are for pointy-topped hexes, and some of the algorithms use a helper function from the main page:

```function pixelToPointyHexFraction(x, y) {
let q = sqrt(3) / 3 * x + -1/3 * y;
let r = 2/3 * y;
return {q, r};
}
```

The first algorithm is the `hex_round` function from the main page. It uses three `round()` calls, three `abs()` calls, and two if/else branches.

If you look closely at the lines below or above the white hexagon, the boundary between the blue and red hexagons is not perfectly straight. There’s a (literal) edge case there that `hex_round()` treats inconsistently due to numerical precision / float errors. A reader says that changing `2/3 * y` to `(1 - 1/3) * y` in the `pixelToPointyHexFraction` code will help.

### 1.1. Charles Chambers#

Back in 2013, Charles Chambers sent me pixel to hex conversion code that has five `floor()` calls. First, divide `x` and `y` by `size * sqrt(3)`; then find `q,r` with:

```temp = floor(x + sqrt(3) * y + 1)
q = floor((floor(2*x+1) + temp) / 3);
r = floor((temp + floor(-x + sqrt(3) * y + 1))/3);
```

How does it work? Charles uses the `floor()` function to divide space into rows of rhombuses. Two rhombuses and two half-rhombuses make one hexagon. If you look at subexpressions in the “inner” calls to `floor()`, `2 * x`, `x + sqrt(3) * y`, and `-x + sqrt(3) * y`, you’ll notice that they’re dot products of `(x, y)` with the three basis vectors aligned with the hex grid. Each “outer” call to `floor()` combines two of the dot products.

If you’re using this for your own project, note that the `q, r` here are for a different axial form than the one I use in my guide, but I’ve modified my sample code here to match my guide.

### 1.2. Kenneth Shaw#

Kenneth Shaw posted a simplification of Charles Chambers’s algorithm:

### 1.3. James McNeill#

James McNeill’s site playtechs has a great hex grid guide including pixel to hex. He uses two separate affine transformations, one that makes `q` easy to calculate and one that makes `r` easy to calculate. There are six `floor()` calls.

#### 1.3.1. Eric Gradman#

Eric Gradman’s numpy code is an implementation of the playtechs algorithm:

#### 1.3.2. Saevax#

Saevax’s method is based on the playtechs hex guide, inlining and simplifying the code:

### 1.4. Justin Pombrio#

Justin Pombrio has a visual explanation of his algorithm, which elegantly has five calls (three `ceil`, two `round`):

### 1.5. BorisTheBrave#

BorisTheBrave’s algorithm is a variant of Justin Pombrio’s (two `ceil`, one `floor`, two `round`):

### 1.6. Mark Steere#

Mark Steere’s method looks elegant, with five `floor()` calls:

### 1.7. Jacob Rus#

Jacob Rus’s algorithm has three `round()`, two `abs()`, and one `if`. His page has diagrams, interactive demos, and code showing how it works.

### 1.8. vaxquis#

vaxquis sent me some code for pixel to hex, with each hexagon formed out of one rhombus and two triangles. There are two `floor()` for the rhombus and two `if` to handle the triangles.

## 2  Guess and test#

If you can somehow guess a location within a hex of the true answer, you can then correct the guess. Scan its neighbors and itself, and pick the one closest with Euclidean distance. This works because a regular hex grid also happens to satisfy the Voronoi property: the hexagon contains all points that are closer to its center than to any other hexagon center.

Unlike the geometric algorithms listed above, guess and test doesn’t require you to use cube/axial coordinates. It works the same with offset or doubled coordinates.

## 3  Pixel map#

The geometric algorithms above work on pure polygons, but they don’t always match up with a pixel grid. There are three issues, two of which are fixed easily:

The first issue is that you may need to adjust the x, y to point to the center of the pixel instead of the top left of the pixel. Do this by calling `pixelToHex(x + 0.5, y + 0.5)`.

The second issue is that if you want to align to integer pixel boundaries you will need to adjust the width or height of the hexagon, one of which has a sqrt(3) in it. In this diagram you can see that of the hexagons is slightly different in shape and alignment because the width has a sqrt(3) (non-integer value) in it:

To solve this we can stretch or shrink the hexagons slightly to make them line up with the pixel grid, so that they all are the same shape. The math on the main page doesn’t support this, but the implementation page does. In this case I set the width to be 10 ÷ (sqrt(3) ⨉ 6) times what it normally would be:

The third issue is that these hexagons may not look nice (symmetric, etc.), and may not match your desired pixel boundaries, especially if you have pixel art. The flaws are more easily seen when the pixels are large relative to the hexagons:

For more control, work directly with pixels. Compute or decide on the answer per pixel and store it in an array or bitmap. Hand tune the boundaries to make them look nice. You can get precise control so that it can fit your pixel grid.

A global pixel map would be to store the answer in an array or bitmap the size of the screen or game map. An array would contain pairs (`q:int, r:int`), or a bitmap could contain `q` in the red channel and `r` in the green channel. However, this array may be large.

For many hexagon sizes, especially if adjusting for pixel art, the pixel boundaries will repeat in an offset pattern:

If you have a repeating pattern, you can use a local pixel map. Each pixel inside the pixel map will be an offset relative to the hexagon at the top left of the pixel map. You’ll need to:

1. Calculate which rectangle the pixel is in.
2. Calculate which hexagon is at the top left of that rectangle.
3. Calculate which pixel within the rectangle.
4. Look up in the pixel map the hexagon offset relative to the top left hexagon.
5. Add that pixel’s offset to the top left hexagon.

For example you might determine rectangle’s top left is at hexagon `q:5, r: 1`. Then you look at the pixel within the rectangle, and see that its offset is `q:-1, r: +1`. Then you add the two, and get `q:4, r: 2` as the final hexagon in the lookup.

It’s more steps but the main advantage is that a local pixel map will be much smaller than a global pixel map, and it will also work on an infinite map. You may be able to use a rectangle even smaller than the one I show in the diagram. The disadvantage of the local pixel map is that it only works when all the hexagons follow a repeating pattern.

Another advantage of a pixel-perfect approach, whether global or local, is that you can handle the borders between hexagons. David Johnson has a multipage guide for hex grids that builds a global pixel map. He takes into account the width of the borders, explains the theory, and has interactive demos.

A system I used for an old game encodes the pixel boundary in an array. Many of the algorithms listed below use the repeating rectangle approach for lookups.

## 4  More algorithms#

By looking at the geometry of hexagons you can narrow down a pixel location to either one, two, or three hexagons, typically by dividing hexagons into smaller shapes. You can then use the edges between hexes to determine which subshape the pixel coordinate is on. There are a variety of shapes you can use. Here are some articles to read with details:

Do you have any other algorithms for this list?

The visual tests on this page are generated by this source code.

Email me , or tweet @redblobgames, or comment: