计算2点之间的网格距离 [英] Calculate distance on a grid between 2 points

问题描述

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

I need to calculate the distance on a grid between 2 points. The movement allowed is horizontal and vertical as well diagonal to the next neighbor (so 45 degree rotations).

所以曼哈顿距离不是一个选项。欧几里德距离也不是一个选项，因为它不会沿着网格正确移动，这可能导致一个较低的值（如红线所示）。

So Manhattan distance is not an option. Also Euclidean distance is not an option cause then it does not move correct along the grid which can result in a to low value (as in the red line).

我'我希望得到距离，如绿色线从一个单元格移动到另一个单元格。

I'm looking to get the distance as in the green line where it moves from cell to cell.

公式最好是快速的。

推荐答案

这很简单：

• 你向对角线方向移动直到你'在同一行或同一列。这将是min（ dx ， dy ）步骤。

让我们称之为 d （对角线步骤）

Let's call this d (for diagonal steps)

然后你朝着目标直线前进。这将是最大值（ dx ， dy ） - d 步骤。

Then you move on a straight line towards the goal. This will be max(dx, dy) - d steps.

让我们叫这个 s （直接步骤）

Let's call this s (for straight steps)

距离是√2× d + s 。

The distance is then √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点之间的网格距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！