java - 计算两点之间网格上的距离

Question

我需要计算网格上两点之间的距离。允许的移动是水平和垂直的以及与下一个邻居的对角线(因此旋转 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;
}