Triangular Grid Math

This little applet is inspired by this Amit/RedBlobGames blog post on hexagonal grids. It also follows up on an earlier blogpost of theirs about Triangle Grids, which sadly doesn't include any interactivity.

I wanted to better familiarize myself with Vue and Javascript rendering, to extend my graphics work for a Pen Plotter and 3D CPU Renderer.

Purpose

While working on Truchet tiles and Marching Squares implementations, I found myself quite comfortable with a square grid. Take any rectangle, and subdivide it into squares (rectangles with all sides the same), and use their Cartesian (x,y) coordinates to refer to each individual square. Since I was working on plotting the results, and the pen starts at the upper left corner of the page, I found that this was a convenient origin point, with x-coordinate increasing left-to-right, and the y-coordinate increasing downwards.

Cartesian square grid

I then wanted to extend these approaches to other regular grids. Surprisingly, what coordinate system to use is not a trivial decision. As mentioned above, the choices for hexagons are many, one should choose the coordinate system that works best.

What about triangles though? The plane can be partitioned into equilateral triangles trivially. Here I orient them such that one edge is horizontal. I get two triangle orientations; one with pointing up, the other pointing down. But how do we index into them? Specifically, I am looking for a unique integer-based coordinate for each triangle, and an easy mapping between the coordinate and the corresponding triangle. Ideally, the coordinate system should be translation-invariant (the coordinates should change between adjacent triangles under the same pattern, no matter where in the grid the triangle exists), they should allow for an easy creation of the grid, and it should lead to easy human interpretability.

Equilateral triangular grid

Skewed-square Grid : xyR

For this first coordinate grid, we take the square grid, and skew it so that it forms a grid of parallelogram with 60°-120° angles. We then split each parallelogram along its shorter diagonal, to form two triangles, an upper and a lower one. We refer to each triangle by the (x,y) coordinate of its parallelogram, along with a third R coordinate, which is 0 for the lower triangle, and 1 for the upper triangle, producing a three-dimensional (x,y,R) coordinate for each triangle.

The resulting grid sets the triangles with the same x-coordinate on an angle, which leads to some awkwardness. For example, the trivial for-loop to generate the grid results in a parallelogram-shape.

An obvious observation is that while x- and y- coordinates can vary over all integers $ℤ$ , the R-value can only be chosen from the set ${0, 1}$ . So we have produced a coordinate system that spans $ℤ ⨯ ℤ ⨯ {0, 1}$ .

What about determining whether two triangles are next to each other? For this we look at how the coordinates change when crossing from one triangle to another. We have to consider the case of the upwards-pointing triangle separately from the downwards-pointing triangle.

We notice that multiple coordinates can change when moving across and edge, depending on the direction. This makes adjacency logic somewhat cumbersome, and we might need to move to a different coordinate system to solve that problem.

Three-axis Grid: xyz

Another idea is to notice that each triangle lives on three separate axis. As shown above, the triangles with the same x-value appear on a diagonal, whereas triangles with the same y-value appear on the same horizontal row. There is a third diagonal, which we can denote with the value z.

So let's redefine our grid using this x,y,z system. There is a simple conversion from the xyR coordinates to xyz coordinates, given by z:=x-y+R. But there is a bit of a catch. We can't just loop over all x-, y-, and z- values to get the resulting grid, since not all combinations of these values produce a valid triangle coordinate. Just like with the xyR coordinates above, we don't really have a full $ℤ^{3}$ space; the dimensions have to have a constraint.

To discover what this constraint is, let's look at how the coordinates would change in this system going from one triangle to its neighbors. We have to keep in mind that the tiling contains both upwards- and downwards-pointing triangles, so the rules have to be explored for both, though they end up being inverses of each other along the three axes.

What becomes apparent is that when moving one step away from an upwards-pointing triangle, we change one of the coordinates by one. The x-coordinate decreases by one, while the y- and z- coordinates increase by one. So the value $- x + y + z$ increases by one.

In the other case, for the downwards pointing triangle, the math is flipped. We, again, change one coordinate. This time the x-coordinate increases, whereas the y- and z- coordinates decrease, so the value of $- x + y + z$ decreases by one.

Another critical observation is that moving across the grid, we keep alternating between upwards- and downwards-pointing triangles. So the value of $- x + y + z$ keeps flipping back and forth by one value. Consequently, that is our constraint; the value of $- x + y + z$ is restricted to only two values — 0 or 1. So we have that $- x + y + z \in {0, 1}$ .

Here is the resulting grid, rendered using the xyR for-loop above, then converting the coordinates to xyz.

What is great about this representation is that calculating the distance between two triangles (defined as the minimum number of edges one needs to cross) is trivial in the xyz system. We merely need to count how many times each coordinate has changed. In other words:

d (t 1, t 2) := | {t 1}_{x} - {t 2}_{x} | + | {t 1}_{y} - {t 2}_{y} | + | {t 1}_{z} - {t 2}_{z} |

Distance measure

The row-column coordinate system: yb

Finally, we notice that our triangles are arranged in diamond-shaped columns, so we wonder if there is a way to express the coordinates of a triangle with a two-dimensional (row, column) coordinate. Turns out this is possible if we preserve the y-coordinate from the previous sections, but we define a new coordinate b := x + z. Since we have removed a whole dimension, we should be free to loop over the y- and b-values in a for-loop, to produce a very neat looking grid of triangles.

However, while this representation is very easy to loop over, we might want to translate back to the xyR or xyz coordinate system for other purposes. Turns out that this conversion is not very pretty looking. Not pretty at all!

Just as before, we want to consider adjacency. Notice that triangles along a b-column vary in the y-coordinate by one, whereas the distance changes more than that. Specifically, consider two triangles trouching vertically at a point, their distance is 3, whereas their coordinates differ only by 1. This makes distance math convoluted. It is best to convert to the xyz coordinate system to compute distance.

All Three Coordinates In One

Let's do an overview of the three coordinate systems. We care about translating between them, so here is a conversion table.

Coordinate conversions between the three systems
	From xyR	From xyz	From yb
to xyR		$\begin{matrix} x & = & x \\ y & = & y \\ R & = & z - x + y \end{matrix}$	$\begin{matrix} x & = & ⌊ \frac{b + y}{2} ⌋ \\ y & = & y \\ R & = & (b + y) % 2 \end{matrix}$
to xyz	$\begin{matrix} x & = & x \\ y & = & y \\ z & = & x - y + R \end{matrix}$		$\begin{matrix} x & = & ⌊ \frac{b + y}{2} ⌋ \\ y & = & y \\ z & = & ⌊ \frac{b + y}{2} ⌋ - y + (b + y) % 2 \end{matrix}$
to yb	$\begin{matrix} y & = & y \\ b & = & 2 x - y + R \end{matrix}$	$\begin{matrix} y & = & y \\ b & = & x + z \end{matrix}$

As outlined above, generating the grid is easiest in yb coordinate system, since in most applications we want to display discrete rows and columns of triangles. We will benefit most by using the xyz coordiante system to compute distances between triangles. Finally, the xyR coordinate system makes it trivial to figure out whether a certain triangle points upwards or downwards, by referring to the R-coordinate.