Geometry with Hex Coordinates 13


screen_136

\( \newcommand{\bv}[1]{{\bf #1}} \) \( \newcommand{\bperp}{{\bf perp}} \) \( \newcommand{\bproj}{{\bf proj}} \)

There is surprising little information available on hex-coordinates, despite how many games use hex grids. In this article I will explain some of the math so that you can do basic geometry in a hex grid, and design more elegant algorithms for your hex-grid games.

There are different coordinate systems for hexes of course. (For a very informative explanation, with many interactive examples, see Amit Patel’s wonderful guide Hexagon Grids.) We will work with an axial coordinate system, which is illustrated in the figure below.

screen_122

From time to time we will use an extra coordinate. This coordinate can be calculated from the other two, like this:

$$z = -(x + y)$$

So in fact \(x + y + z = 0\). Any equation using the \(z\)-coordinate can be rewritten using \(x\) and \(y\)-coordinates alone. However, some equations are much cleaner (and the symmetry much more obvious) when we use the \(z\)-coordinate.

Here I will use both notations \([x, y, z]\) and \([x, y]\) to denote the same point. A point or vector will be displayed in bold, like this: \(v\), and integer and real values like this: \(k\).

  • The \(x\)-axis is where \(y = 0\). It’s the horizontal orange axis in the figure.
  • The \(y\)-axis is where \(x = 0\). It’s the skew vertical orange axis in the figure.
  • The \(z\)-axis is where \(z = 0\). It’s the skew vertical yellow axis in the figure.

Coordinates work like (integer) vectors

We can view each point as the offset from the origin and from there treat points as vectors. These vectors work just like point vectors in the Cartesian coordinate system. It is useful to name the unit vectors that align with the axes with the directions they represent:

  • \(\bv {e} = [1, 0, -1] \)
  • \(\bv {ne} = [0, 1, -1] \)
  • \(\bv {nw} = [-1, 1, 0] \)
  • \(\bv {w} = [-1, 0, 1] \)
  • \(\bv {sw} = [0, -1, 1] \)
  • \(\bv {ew} = [1, -1, 0] \)

If we start from a point, and go 3 units east, we arrive at a new point, which we can now calculate as follows:

$$\bv v + 3\bv{e} = [x, y, z] + 3 \times [1, 0, -1] = [x, y, z] + [3, 0, -3] = [x + 3, y, z – 3]$$

If we instead move 2 units ne, we calculate the new point as follows:

$$\bv v + 2\bv {ne} = [x, y, z] + 2 \times [0, 1, -1] = [x, y, z] + [0, 2, -2] = [x, y + 2, z – 2]$$

Any point can be reached from another point by moving a certain amount of units east (possibly negative), and a certain amount north-east. So we can always find integers \(m\) and \(n\) sothat for any two points u and v, we have

$$\bv u + m \bv e + n\bv {ne} = \bv v$$

Using a little algebra, we rewrite the above as

$$\bv u + [m, n, -m – n] = \bv v$$

Or

$$[m, n, -m – n] = \bv v – \bv u$$

In other words, the offset (translation) from \(\bv u\) to \(\bv v\) can be found by subtracting \(\bv u\) from \(\bv v\).

Distance and magnitude

The hex-distance between two cells is the number of cells you have to traverse if you move from cell to cell from one point to the next. This is generally different from the Euclidean distance between the points; it is similar to the taxicab distance for rectangular coordinates.

The hex distance from any point to the origin can be calculated as half the sum of the absolute values of the coordinates:

$$d([x, y, z], [0, 0, 0]) = \frac{|x| + |y| + |z|}{2}$$

screen_124

The distance between any two points \(\bv{v}_1\) and \(\bv{v}_2\) is the same as the distance of \(\bv{v}_1 – \bv{v}_2\) from the origin:

$$d([x_1, y_1, z_1], [x_2, y_2, z_2]) = d([x_1 – x_2, y_1 – y_2, z_1 – z_2], [0, 0, 0])$$

$$ = |x_1 – x_2| + |y_1 – y_2| + |z_1 – z_2|$$

It is convenient to define the magnitude of a hex vector as the distance of that point from the origin:

$$|[x, y, z]| = d([x, y, z], [0, 0, 0]) = \frac{|x| + |y| + |z|}{2}$$

We can then rewrite the distance equations as:

$$d(\bv{v}_1, \bv{v}_2) = |\bv{v}_1 – \bv{v}_2|$$

The equation of a line

Lines in hex-coordinates work similar to lines in Cartesian coordinates. We will only consider the “proper” lines, that is, were there are no holes in the lines, and all points in the line have exactly two neighbors.

There are only three proper lines through any given point.

The three lines through the origin are given by the following equations:

  • \(x = 0\)
  • \(y = 0\)
  • \(z = 0\)

If we change the equations slightly, we get lines through arbitrary points:

  • \(x = k\)
  • \(y = k\)
  • \(z = k\)

screen_125

The figure above shows tree lines: \(x = 2\) in orange, \(y = 2\) in yellow, and \(z = 2\) in green.

The value \(k\) corresponds with the number of unit cells the line has been translated in the positive direction from the axis to which it is parallel. This makes it very easy to write the equation of a line with inspection.

Note a few things:

  • Lines of the form \(x = 0\) are all parallel to the \(y\)-axis. Thus, all lines of the form \(x = k\) are parallel to each other.
  • Lines of the form \(y = 0\) are all parallel to the \(x\)-axis. Thus, all lines of the form \(y = k\) are parallel to each other.
  • Lines of the form \(z = 0\) are parallel to neither the X nor Y axis. Thus, all lines of the form \(z = k\) are parallel to each other.
  • We can rewrite the equations of lines \(z = k\) as \(x + y = -k\).
  • Two distinct points on a line always have exactly one coordinate in common. If the line is of the form \(x = k\), then they have the \(x\)-coordinate in common, and so on.

These facts make it very easy to write the equations of a line by inspection:

  • Determine whether the line is parallel to the \(x\)-axis, the \(y\)-axis, or neither. From this determine whether the form is \(x = k\), \(y = k\), or \(z = k\)
  • Now calculate the (signed) distance \(k\) from the origin along the axis (the same as the variable in the equation).

The intersection of lines

To determine the intersection of two lines in hex space is extremely easy. As always in geometry, we have several cases:

  • The lines are coincident. In this case, the solution is of course all the points on the two lines (which are really one line).
  • The lines are not-coincident, but parallel. This is of course when the lines have the same form of the equation: both are \(x = \ldots\), or \(y =\ldots\) , or \(z = \ldots\). In this case, there are no solutions.
  • The lines are not parallel. In this case, the equations have different forms. The solution is a single point.

The last case is the one we are really interested in. As an example, let’s find the intersection of the lines \(x = 3\) and \(y = 5\). The intersection is simply \([3, 5]\). The augmented point is then \([3, 5, -8]\) — remember, \(z = -x – y\). More generally, we can just fill in the two coordinates from the corresponding equations:

  • If we have \(x = k\), the \(x\)-coordinate is \(k\).
  • If we have \(y = m\), the \(y\)-coordinate is \(m\).
  • If we have \(z = n\), the \(z\)-coordinate is \(n\).

In general we have two equations, so we have two coordinates of the point. The third can be calculated from \(x + y + z = 0\).

Here are two more examples:

\(x = -3\), \(z = 3\). The intersection is \([-3, \ldots, 3]\), or after we calculated the \(y\), \([-3, 0, 3]\).

screen_126

\(y = -2\), \(z = 2\). The intersection is \([\ldots, -2, 2]\), or after we calculated the \(x\), \([0, 2, -2]\).

screen_127

Half-planes

A half-plane is all the points that fall on one side of the line, and includes the line itself as well.

Since there are only three types of proper line, there are also only six types of proper half-planes (one on each of the two sides of each line).

Their equations are given below:

  • \(x \geq k\) and \(x \leq k\)
  • \(y \geq k\) and \(y \leq k\)
  • \(z \geq k\) and \(z \leq k\)

Half-planes are useful to form polygons. Any convex polygon is the intersection of half-planes. This is true for normal Cartesian coordinates, as well as hex-coordinates.

screen_128

$$x \geq 2$$

screen_129

$$x \leq 2$$

Triangles

Triangles are bound by three lines, no two of which are parallel.

The equation for an up-triangle is the following:

$$(x \geq k) \cap (y \geq m) \cap (z \geq n)$$

And for a down-triangle, we have

$$(x \leq k) \cap (y \leq m) \cap (z \leq n)$$

screen_130

The figure above shows two triangles. The up-triangle has this equation:

$$(x \geq 0) \cap (y \geq 1) \cap (z \geq -3)$$

and the down triangle has this equation:

$$(x \leq 0) \cap (y \leq -1) \cap (z \leq 3)$$

By taking the equations of the lines of the triangle sides two at a time, we can easily calculate the three vertices of the triangle:

  • \([k, m, \ldots] \rightarrow [k, m, -k -m]\)
  • \([k, \ldots, n] \rightarrow [k, -k – n, n]\)
  • \([\ldots, m, n] \rightarrow [-m – n, m, n]\)

screen_131

The length of the sides can now be calculated. The distance between the first two vertices above is:

$$d([k, m], [k, -k – n] = \frac{|k – k| + |m + k + n| + |-k – m – n|}{2} = |k + m + n|$$

In fact, the other two sides have the same length.

  • In hex-space, all triangles are equilateral.

We can just as easily get the equations of a triangle from the vertices. But there is a catch:

  • not any three points form a (proper) triangle.

Three points form a triangle only when each pair of points have a coordinate in common, and the common coordinate is a different one (from x, y, or z) for each pair. In other words, two points must have their \(x\)-coordinate in common, two points must have their \(y\)-coordinate in common, and two points must have their \(z\)-coordinate in common.

To write the equation for the triangle, simply find the common \(x\)-coordinate \(k\), the common \(y\)-coordinate \(m\), and the common \(z\)-coordinate \(n\), determine whether the triangle is up or down, and then write the appropriate equation:

$$(x \geq k) \cap (y \geq m) \cap (z \geq n)$$

or

$$(x \leq k) \cap (y \leq m) \cap (z \leq n)$$

The triangle is up if the \(y\)-coordinate of the vertex not on the line \(y = m\) is bigger than \(m\). The \(y\)-coordinate of that vertex is \(-k -n\). So the triangle is up if \(-k -n > m\); otherwise, it’s down.

Quadrangles

Quadrangles are bounded by four lines, and thus can be written as the intersection of four half planes. As with triangles, it is easy to determine the vertices from the equation, and vice versa, although you need to take a bit more care because at least one pair of lines will be parallel.

All quadrangles in hex-space are trapezoids (for people outside the US: trapeziums).

I give a few examples:

Trapezoid:

$$(x \geq -3) \cap (z \geq -3) \cap (y \leq 2) \cap (y \geq 0)$$

screen_132

Parallelogram:

$$(x \geq -3) \cap (x \leq 3) \cap (y \leq 2) \cap (y \geq 0)$$

screen_133

General convex polygon

In hex space, convex polygons can have up to six sides. The general equation for any convex polygon is the intersection of six half-planes:

$$(k_1 \leq x \leq k_2) \cap (m_1 \leq y \leq m_2) \cap (n_1 \leq z \leq n_2)$$

Note that we can also use this form of equation to represent triangles and quadrangle, although the equations then are not unique. For example, the following two equations represent the same triangle:

$$(-4 \leq x \leq 100) \cap (-4 \leq y \leq 100) \cap (-4 \leq z \leq 100)$$

$$(-4 \leq x \leq 200) \cap (-4 \leq y \leq 200) \cap (-4 \leq z \leq 200)$$

From the general equation we can make the following observations:

  • Pentagons have two pairs of sides that are parallel.
  • Hexagons have three pairs of sides that are parallel.

screen_134

The figure above shows an irregular hexagon with the equation (the shape includes both orange and yellow points, I made the borders yellow so that it is easier to see the lines that form the sides):

$$(-4 \leq x \leq 3) \cap (–1 \leq y \leq 2) \cap (-1 \leq z \leq 4)$$

Regular Hexagons

The equation of a regular hexagon with centre c can be written in a very simple form:

$$|\bv v – \bv c| \leq r$$

screen_135

In the hex world, all points within a distance r of some point form a regular hexagon. The image above shows a hexagon with centre \([1, 1]\) and radius \(r = 2\).

Rotation

Using three coordinates, there is an easy trick to rotate a point by 60 degrees around the origin: rotate the coordinates left, and change all the signs:

$$[x, y, z] \rightarrow [-y, -z, -x]$$

(From here it’s easy to remove the \(z\)-coordinate, as usual, to find:

$$[x, y] \rightarrow [-y, x + y]$$

By applying the trick above repeatedly, we can find similar expressions for points rotated by 120, 180, 240, and 300 degrees.

It is also easy to see immediately whether a point is another point rotated by some multiple of 60. The two points must have the same coordinates (or the same negative coordinates), in the same order, but potentially shifted:

  • \([2, 3, 4]\) and \([3, 4, 2]\) (Yes)
  • \([2, 3, 4]\) and \([2, 4, 3]\) (No – not in same order)
  • \([2, 3, 4]\) and \([-4, -2, -3]\) (Yes)
  • \([2, 3, 4]\) and \([-4, 2, 3]\) (No – signs not consistent)

We can rotate a point \( n \times 60\) degrees around any point \(\bv {c}\):

$$R_{60n}(\bv {v} – \bv {c}) + \bv {c}$$

Reflection

Reflection about \(x = 0\) (\(y\)-axis)

  • Flip \(x\), keep \(z\), recalculate \(y = -x – z\)

Reflection about \(y = 0\) (\(x\)-axis)

  • Flip \(y\), keep \(z\), recalculate \(x = -y – z\)

Reflection about \(x + y = 0\) (\(z\)-axis)

  • Flip both \(x\), \(y\), and \(z\)

With suitable translations, we can reflect a point about any line.

For example, to reflect point about the line \(x = 1\), we translate the point by \([-1, 0]\), reflect it about the \(y\)-axis, and then translate it back by \([1, 0]\).

$$R_Y(\bv {v} – \bv {e}) + \bv{e}$$


avatar

About Herman Tulleken

Herman Tulleken is a freelance game developer, toolmaker, and co-founder of Gamelogic. He thinks computers are a necessary evil to make games, and sees frying a CPU or two in the process as a worthy sacrifice.


Leave a comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

13 thoughts on “Geometry with Hex Coordinates