Grid parts and relationships

This guide will show coordinate systems for tiles (faces), vertices (corners), and edges for square, hexagon, and triangle^[1] grids. There are algorithms for going from a tile to its corners, an edge to its tiles, and many others. For a more detailed guide to hexagons, see my guide to hexagonal grids. For more on square grids, see my pages on edges, line-drawing, and circle fills.

Part A (black)	Part B (red)
	Face	Edge	Vertex
Face	Neighbors:	Borders:	Corners:
Edge	Joins:	Continues:	Endpoints:
Vertex	Touches:	Protrudes:	Adjacent:

The names and definitions here are arbitrary. This page isn't about the way to set up relationships, but one way to set up relationships. You'll want to adapt these for your own project. For example, you might choose to have neighbors and adjacent include diagonals. You might choose continues to include edges that aren't colinear. You might choose additional relationships. I hope this page gives you ideas for designing your own system for your project.

This page is an updated version of my 2006 guide to grid parts^[2].

 1  Square grids#

Square grids are common. In both 2D and 3D graphics systems, we have to transform “world” coordinates into “screen” coordinates and back. With grids, we also have to transform “grid” coordinates into “world” coordinates and back. The world↔screen transform will be different for a top-down or side or isometric view, but the grid↔world transform works the same. This page covers the grid coordinates only and not the transforms.

 1.1. Coordinates#

 1.2. Relationships#

Each of these 9 relationships can be expressed as taking an input and generating a list of outputs. For some types of input there is a different rule for each s value.

 2  Hexagon Grids#

In this article, I use pointy-top hexagons, but the math works the same if you want flat-top hexagons. To construct hexagon coordinates, we can start with a square grid and morph it into a hexagon grid:

This is the "axial" coordinate system from my comprehensive hexagonal grid guide^[3]. That page has more coordinate systems and many more algorithms.

 2.1. Coordinates#

 2.2. Relationships#

For squares and triangles, I defined the Continues relation for collinear edges, but with hexes there aren't any. It would be reasonable to define them to be non-collinear edges. Don't take the relations here as the way to define the relations; they're one way to define them. Adapt the rules here to match the needs of your project.

 3  Triangle Grids#

Triangles are common in 3d graphics but are less commonly used for game maps. In this article I use triangles pointed up and down, but the math works the same if your triangles point left and right.

Other variants:

• GridLogic's library^[4] encodes L and R as 1 and 0.
• mhwombat's scheme^[5] is similar to "doubled coordinates" for hexagonal grids. It skips some coordinates like (0,1) and encodes the L, R annotations into the q,r values.
• For triangle-shaped maps ZenoRogue's scheme^[6] folds a rhombus in half to encode the L, R annotations into the two halves of the rhombus.
• BorisTheBrave writes about a three-lane coordinate system^[7] that is similar to "cube coordinates" for hexagonal grids^[8]. The q, r values from this page become a, b values, and c is computed as 1 - q - r for L triangles and 2 - q - r for R triangles. This is similar to how cube hex coordinates are related to axial hex coordinates, by computing the third value as -q - r.
• Vsevolod Kvachev's post^[9] has several distance functions for triangle grids, including handling diagonal movement.

 3.1. Coordinates#

To convert triangle vertices from grid coordinates to world coordinates, multiply by the axis vectors i and j:

  ⎛ x ⎞     ⎡ i.x j.x ⎤ ⎛ u ⎞
  ⎝ y ⎠  =  ⎣ i.y j.y ⎦ ⎝ v ⎠

Expanded out, that's

  x = i.x * u + j.x * v
  y = i.y * u + j.y * v

To convert triangle face coordinates to world coordinates involves an adjustment. For face (q, r, L/R) first calculate the world coordinates of the lower left vertex, (q, r). Then for an L face, add (1/2 * i, 1/3 * j) to the upper left vertex location. For an R face, add (i, 2/3 * j) to the upper left vertex location. The result will be the center of the face.

To convert from world coordinates to triangle vertices, first find the upper left corner of the rhombus (q, r) using algebra, or by inverting the i.x,j.x,i.y,j.y matrix. The rhombus contains two triangle faces. To determine which face the point is in, look at the edge that divides the two triangles inside each rhombus. If frac(q) + frac(r) < 1.0, the point is on the left of the line, and is therefore in the L face; otherwise it is in the R face.

When working with triangles, treat vertices as primary, and face centers as secondary. This is the opposite of how we treat hexagons.

Distance on a triangle grid is something I explore here^[10]. I haven't worked much with triangle grids and don't know if this is the best way to approach it. This article from symbo1ics^[11] has more math for triangle grids.

 3.2. Relationships#

 4  More#

For implementation of the Tile, Edge, Vertex data structures, I usually use a struct with public fields, q and r being integers and s being a symbol (:L in Ruby, 'L in Lisp) or a character ('L' in C or C++ or Java or Rust) or a one-character string ('L' in Python). Each of the relationship algorithms is a function that takes a part as input and returns a list of parts as output. Parts that have s variants can be handled using switch or pattern matching. I made a JavaScript implementation to implement the diagrams on this page.

What else would you like to see me include in this document? Was anything confusing? Incomplete? Incorrect? Let me know.

There are some things I didn't find a place for, but might be of interest. Mathematicians have found five types of grids in 2D space^[12]: squares, triangles, hexagons^[13], rectangles, and parallelograms. However only squares, triangles, and hexagons are regular polygons. Spiral Honeycomb Mosaic^[14] (search the page for "Spiral Honeycomb Mosaic") is an interesting way to assign numbers to hexagons in a hexagonal grid. It results in bizarre properties.