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

math java distance language-agnostic

2022-09-04 21:39:21

我需要计算2点之间的网格上的距离。允许的移动是水平和垂直的，以及与下一个邻居的对角线（因此45度旋转）。

因此，曼哈顿距离不是一种选择。此外，欧氏距离不是一个选项，因为它不能沿着网格正确移动，这可能导致一个较低的值（如红线）。

我希望获得从一个单元格移动到另一个单元格的绿线中的距离。

最好是公式速度快。

enter image description here

答案 1

这很简单：

沿对角线向目标移动，直到您位于同一行或同一列。这将是最小（dx，dy）步长。

我们称之为 d（表示对角线步骤）
然后，您沿着一条直线向目标移动。这将是最大（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;
}

答案 2