# 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.)

click to regenerate

*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.

click to regenerate

*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.