计算2点之间的网格距离

Question

我需要计算2点之间的网格距离.允许的运动是水平的和垂直的,以及与下一个邻居的对角线(所以45度旋转).

所以曼哈顿距离不是一个选择.欧几里德距离也不是一个选项,因为它不会沿着网格正确移动,这可能导致一个低值(如红线所示).

我希望得到的距离就像它从一个细胞移动到另一个细胞的绿线一样.

公式最好是快速的.

Answer 1

这很简单:

• 你沿着对角线向目标移动,直到你要么在同一行或同一列.这将是min(dx,dy)步骤.

  我们称之为d(对角线步骤)

• 然后你朝着目标直线前进.这将是max(dx,dy) - d步.

  我们称之为s(直接步骤)

• 距离是√2× d + s.

在代码中:

double distance(int x1, int y1, int x2, int y2) {
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);

    int min = min(dx, dy);
    int max = max(dx, dy);

    int diagonalSteps = min;
    int straightSteps = max - min;

    return sqrt(2) * diagonalSteps + straightSteps;
}