hexagonal lattice rounding

How do you round coordinates on a hexagonal grid?

definitionhexagonal vs. visual space

definitionrendering transformation

Define the transformation $T\colon ℋ→𝒱$ by
$T = \begin{bmatrix} \cos 0 & \cos \frac π 3 \\ \sin 0 & \sin \frac π 3 \end{bmatrix} = \begin{bmatrix} 1 & \frac 1 2 \\ 0 & \frac {\sqrt 3} 2 \end{bmatrix}.$
This is the transformation that maps points in hexagonal-space coordinates to their visual positions. In particular, $T(ℤ²)$ looks like this (dotted lines annotate hexagonal boundaries):

(insert diagram)

For any $p∈ℋ$ and $q∈𝒱$ , we will say that $p$ renders to $q$ to mean $Tp=q$ ; i.e., $q$ is the visual position of $p$ .

problemhexagonal rounding

Given $p∈ℋ$ , find $p'∈ℤ²⊂ℋ$ so that the (Euclidean) distance between $Tp,Tp'$ is minimized. That is to say, we wish to round $p$ to the nearest point on the hexagonal lattice.

Why is this not a trivial question? Why is the answer not just

(x,y) ↦ ([x], [y])

(apply regular integer rounding to each coordinate)? The problem with this is that it minimizes distance only in regular orthogonal Cartesian space—we’d like to minimize distance in hexagonal space. This is best seen by plotting what it does visually:

DIAGRAM

In particular, in plain $ℝ²$ this collects points into square boxes, which after applying the render transformation turns into rhombi. So this clearly fails, because we’re looking for an algorithm that collects points into hexagonal boxes.

(For an explicit counterexample, take some small $ϵ>0$ , consider the point $p≔(\frac12-ϵ,\frac12-ϵ)∈ℋ$ , whose visual position is $Tp≈(\frac32,\frac{\sqrt 3}2)$ . Naively, this point rounds to $(0,0)$ ; however it is visually actually closer to $(1,0)$ or $(0,1)$ .)

OK, so how do we tackle this? Here’s the approach I came up with—probably not the most elegant, but I think it’s cute.

So, let $p=(x,y)$ be given. We will denote $(u,v)≔Tp$ and also let $p'=(x',y')$ denote the hexagonal-rounded coordinates we are trying to calculate. We will call $x'$ the column and $y'$ the row. Consider two cases based on $y$ :

If $y$ is less than $\frac13$ distance away from its nearest integer, then we say $p$ is in a vertical section of the grid. In these sections the hexagonal boundaries are purely vertical (and column differentiation depends only on the visual position $u$ ). This is the simple case.

We know unambiguously that the row is $y'=[y]$ . To calculate the column, observe that the lattice point at column $0$ renders to $T(0,y')=(\frac{y'}2,\frac{\sqrt 3 y'}2)$ . So, relative to column zero, $q$ is horizontally offset by $u-\frac{y'}2$ , whose nearest integer gives the column number $x'$ .
$(x',y') = \left(u - \frac {[y]} 2, [y]\right).$
If $y$ is more than $1/3$ distance away from its nearest integer, we say $p$ is in a zigzag section of the grid. In these sections we’re trying to differentiate between adjacent rows of hexagons, demarcated by the top/bottom boundaries of hexagons, which are slanted and zigzag-shaped.

To make these regions easier to analyze, let’s transform into yet another space, in which the zigzag hexagon boundaries become purely horizontal or vertical. Define $S\colon ℋ→ℝ²$ by
$S = \begin{bmatrix} 1 & -1 \\ 1 & 2 \end{bmatrix},$
Observe that under this mapping, the vectors parallel to the zigzag boundaries map to horizontal/vertical directions: $S(2,-1)=(3,0)$ , $S(1,1)=(0,3)$ . Here’s how the section $1/3<y<2/3$ looks under this mapping:

DIAGRAM

The neat thing to observe here is that, within the zigzag sections, the original hexagonal cutouts are now just unit half-squares. So we floor each coordinate, sending each square to its bottom-left corner, which we denote $⌊Sp⌋$ .

Back in visual space, each of these corners corresponds to the target hexagon’s left vertex along the zigzag. So let
$(a,b) ≔ V S⁻¹ ⌊Sp⌋.$
At this point the vertical coordinate rounds to the row number $y'=[b]$ , and the horizontal component shifted to the right by $1/2$ aligns with the center of the target hexagon, i.e., the column number $x'=a+1/2$ .