Return to Question

For any two points on a hexagonal grid with integer coordinates there is a unique parallelogram which contains all of the shortest paths (in terms of taxicab norm) between these points. See the picture:

Knowing the coordinates of both points in a hexagonal system $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2)$, how do we find other two vertices of the parallelogram? I mean the general formula.

On the rectangular grid it's very simple. We just switch the coordinates to get the rectangle containing all shortest taxicab paths:

$$(x_1,y_1)~~(x_2,y_2)$$

$$(x_1,y_2)~~(x_2,y_1)$$

What do I know about this parallelogram on a hexagonal grid:

• Its angles are $\pi/3$ and $2 \pi/3$
• Its larger diagonal length is equal to the Euclidean distance between the points:

$$d=\sqrt{a^2+b^2+c^2-ab-ac-bc}$$

With $a=u_1-u_2$, $b=v_1-v_2$, $c=w_1-w_2$.

I accept any convention for hexagonal coordinates, as long as it solves the problem.

The coordinates I use are explained in detail in this question.

Edit

As for the explanation why we need three coordinate axes, see this picture:

There are $6$ intersection points in general, but we need to find the two which are closest to the line, connecting the original points. The intersection points are:

$$(u_1,v_2,0)$$

$$(u_2,v_1,0)$$

$$(u_1,0,w_2)$$

$$(u_2,0,w_1)$$

$$(0,v_1,w_2)$$

$$(0,v_2,w_1)$$

This is why this problem is trivial for rectangular lattice (only two intersection points), but more complicated for hexagonal lattice (six intersection points).

How do I choose the correct two points which define the smallest parallelogram?

For any two points on a hexagonal grid with integer coordinates there is a unique parallelogram which contains all of the shortest paths (in terms of taxicab norm) between these points. See the picture:

Knowing the coordinates of both points in a hexagonal system $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2)$, how do we find other two vertices of the parallelogram? I mean the general formula.

On the rectangular grid it's very simple. We just switch the coordinates to get the rectangle containing all shortest taxicab paths:

$$(x_1,y_1)~~(x_2,y_2)$$

$$(x_1,y_2)~~(x_2,y_1)$$

What do I know about this parallelogram on a hexagonal grid:

• Its angles are $\pi/3$ and $2 \pi/3$
• Its larger diagonal length is equal to the Euclidean distance between the points:

$$d=\sqrt{a^2+b^2+c^2-ab-ac-bc}$$

With $a=u_1-u_2$, $b=v_1-v_2$, $c=w_1-w_2$.

I accept any convention for hexagonal coordinates, as long as it solves the problem.

The coordinates I use are explained in detail in this question.

Edit

As for the explanation why we need three coordinate axes, see this picture:

There are $6$ intersection points in general, but we need to find the two which are closest to the line, connecting the original points. The intersection points are:

$$(u_1,v_2,0)$$

$$(u_2,v_1,0)$$

$$(u_1,0,w_2)$$

$$(u_2,0,w_1)$$

$$(0,v_1,w_2)$$

$$(0,v_2,w_1)$$

This is why this problem is trivial for rectangular lattice (only two intersection points), but more complicated for hexagonal lattice (six intersection points).

How do I choose the correct two points which define the smallest parallelogram?

For any two points on a hexagonal grid with integer coordinates there is a unique parallelogram which contains all of the shortest paths (in terms of taxicab norm) between these points. See the picture:

Knowing the coordinates of both points in a hexagonal system $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2)$, how do we find other two vertices of the parallelogram? I mean the general formula.

On the rectangular grid it's very simple. We just switch the coordinates to get the rectangle containing all shortest taxicab paths:

$$(x_1,y_1)~~(x_2,y_2)$$

$$(x_1,y_2)~~(x_2,y_1)$$

What do I know about this parallelogram on a hexagonal grid:

• Its angles are $\pi/3$ and $2 \pi/3$
• Its larger diagonal length is equal to the Euclidean distance between the points:

$$d=\sqrt{a^2+b^2+c^2-ab-ac-bc}$$

With $a=u_1-u_2$, $b=v_1-v_2$, $c=w_1-w_2$.

I accept any convention for hexagonal coordinates, as long as it solves the problem.

The coordinates I use are explained in detail in this question.

Edit

As for the explanation why we need three coordinate axes, see this picture:

There are $6$ intersection points in general, but we need to find the two which are closest to the line, connecting the original points. The intersection points are:

$$(u_1,v_2,0)$$

$$(u_2,v_1,0)$$

$$(u_1,0,w_2)$$

$$(u_2,0,w_1)$$

$$(0,v_1,w_2)$$

$$(0,v_2,w_1)$$

For any two points on a hexagonal grid with integer coordinates there is a unique parallelogram which contains all of the shortest paths (in terms of taxicab norm) between these points. See the picture:

Knowing the coordinates of both points in a hexagonal system $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2)$, how do we find other two vertices of the parallelogram? I mean the general formula.

On the rectangular grid it's very simple. We just switch the coordinates to get the rectangle containing all shortest taxicab paths:

$$(x_1,y_1)~~(x_2,y_2)$$

$$(x_1,y_2)~~(x_2,y_1)$$

What do I know about this parallelogram on a hexagonal grid:

• Its angles are $\pi/3$ and $2 \pi/3$
• Its larger diagonal length is equal to the Euclidean distance between the points:

$$d=\sqrt{a^2+b^2+c^2-ab-ac-bc}$$

With $a=u_1-u_2$, $b=v_1-v_2$, $c=w_1-w_2$.

I accept any convention for hexagonal coordinates, as long as it solves the problem.

The coordinates I use are explained in detail in this question.

Edit

As for the explanation why we need three coordinate axes, see this picture:

There are $6$ intersection points in general, but we need to find the two which are closest to the line, connecting the original points. The intersection points are:

$$(u_1,v_2,0)$$

$$(u_2,v_1,0)$$

$$(u_1,0,w_2)$$

$$(u_2,0,w_1)$$

$$(0,v_1,w_2)$$

$$(0,v_2,w_1)$$

This is why this problem is trivial for rectangular lattice (only two intersection points), but more complicated for hexagonal lattice (six intersection points).

How do I choose the correct two points which define the smallest parallelogram?

For any two points on a hexagonal grid with integer coordinates there is a unique parallelogram which contains all of the shortest paths (in terms of taxicab norm) between these points. See the picture:

Knowing the coordinates of both points in a hexagonal system $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2)$, how do we find other two vertices of the parallelogram? I mean the general formula.

On the rectangular grid it's very simple. We just switch the coordinates to get the rectangle containing all shortest taxicab paths:

$$(x_1,y_1)~~(x_2,y_2)$$

$$(x_1,y_2)~~(x_2,y_1)$$

What do I know about this parallelogram on a hexagonal grid:

• Its angles are $\pi/3$ and $2 \pi/3$
• Its larger diagonal length is equal to the Euclidean distance between the points:

$$d=\sqrt{a^2+b^2+c^2-ab-ac-bc}$$

With $a=u_1-u_2$, $b=v_1-v_2$, $c=w_1-w_2$.

I accept any convention for hexagonal coordinates, as long as it solves the problem.

The coordinates I use are explained in detail in this question.

For any two points on a hexagonal grid with integer coordinates there is a unique parallelogram which contains all of the shortest paths (in terms of taxicab norm) between these points. See the picture:

Knowing the coordinates of both points in a hexagonal system $(u_1,v_1,w_1)$ and $(u_2,v_2,w_2)$, how do we find other two vertices of the parallelogram? I mean the general formula.

On the rectangular grid it's very simple. We just switch the coordinates to get the rectangle containing all shortest taxicab paths:

$$(x_1,y_1)~~(x_2,y_2)$$

$$(x_1,y_2)~~(x_2,y_1)$$

What do I know about this parallelogram on a hexagonal grid:

• Its angles are $\pi/3$ and $2 \pi/3$
• Its larger diagonal length is equal to the Euclidean distance between the points:

$$d=\sqrt{a^2+b^2+c^2-ab-ac-bc}$$

With $a=u_1-u_2$, $b=v_1-v_2$, $c=w_1-w_2$.

I accept any convention for hexagonal coordinates, as long as it solves the problem.

The coordinates I use are explained in detail in this question.

Edit

As for the explanation why we need three coordinate axes, see this picture:

There are $6$ intersection points in general, but we need to find the two which are closest to the line, connecting the original points. The intersection points are:

$$(u_1,v_2,0)$$

$$(u_2,v_1,0)$$

$$(u_1,0,w_2)$$

$$(u_2,0,w_1)$$

$$(0,v_1,w_2)$$

$$(0,v_2,w_1)$$