Minimum Distance Between Two Points in a Nonlinear Triagonal Lattice

This is a short post, somewhat related to this one. I had a hard time figuring this out, particularly because there weren't any good search results for the obvious terms. Hopefully the post improves searchability.

Consider a nonlinear lattice like the following. (I am calling it nonlinear because the coordinates are not linear, for example we would expect (1, 2) to be (0, 2) because it is twice the point (0, 1), etc.)

In a linear system all points along the marked lines, and those along all lines parallel to them, must be multiples of each other.

We want to find a formula for calculating the distance between two arbitrary points, naturally without leaving the lattice. This answer on the math stackexchange goes in the right direction, it gives us a formula for calculating the distance between two points in a linear lattice. It's well written and I don't want to pointlessly repeat it. The gist is that we represent an n-dimensional grid as a subset L of Z^(n + 1). For a two-dimensional grid we can map a linear point (x, y) to (x, y, -x-y) in L. The distance formula is then

d(p, q) = max(0, p.x - q.x) + max(0, p.y - q.y) + max(0, p.z - q.z)

The important point that it doesn't make is the often trivial conversion from nonlinear to linear coordinates. For example, to convert nonlinear coordinates of the above lattice into linear ones:

(x, y) --> (x - floor(y / 2), y)

This allows us to use the above distance calculations with nonlinear coordinates by simply converting them temporarily.

Distance between randomly generated points. The value in braces is the Manhattan distance.

As always, to take a look at the code behind the illustrations on this post either follow the "Edit on github" link at the top or open your devtools, its plain vanilla non-minified JavaScript.