六边形网格上的两个六边形之间的距离

Question

我有一个六边形网格:

使用模板类型坐标T.如何计算两个六边形之间的距离？

例如:

dist((3,3),(5,5))= 3

dist((1,2),(1,4))= 2

Answer 1

首先应用变换(y,x)| - >(u,v)=(x,y + floor(x/2)).

现在面部邻接看起来像

 0 1 2 3
0*-*-*-*
 |\|\|\|
1*-*-*-*
 |\|\|\|
2*-*-*-*

设点为(u1,v1)和(u2,v2).设du = u2 - u1和dv = v2 - v1.距离是

if du and dv have the same sign: max(|du|, |dv|), by using the diagonals
if du and dv have different signs: |du| + |dv|, because the diagonals are unproductive

在Python中:

def dist(p1, p2):
    y1, x1 = p1
    y2, x2 = p2
    du = x2 - x1
    dv = (y2 + x2 // 2) - (y1 + x1 // 2)
    return max(abs(du), abs(dv)) if ((du >= 0 and dv >= 0) or (du < 0 and dv < 0)) else abs(du) + abs(dv)