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

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;
}

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

Calculate distance on a grid between 2 points

java

math

language-agnostic

distance