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

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).

我需要计算网格上两点之间的距离。允许的运动是水平的、垂直的以及对角线到下一个邻居(所以是45度旋转)。

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).

所以曼哈顿距离不是一个选择。欧几里得距离也不是一个选项，因为它不能沿着网格正确移动，从而导致a值低(如红线)。

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

我想要得到的距离，就像绿色的线，它从一个单元移动到另一个单元。

It's preferred that the formula is fast.

最好公式是快的。

1 个解决方案

#1

This is pretty simple:

这是非常简单的:

• You move diagonally towards the goal until you're either on the same row or same col. This will be min(dx, dy) steps.

  你沿着斜线向目标移动，直到你在同一行或同一行，这是最小(dx, dy)步。

  Let's call this d (for diagonal steps)

  我们称它为d(对角线)

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

  然后你沿着一条直线向目标移动。这是max(dx, dy) - d阶。

  Let's call this s (for straight steps)

  我们称它为s(直步)

• The distance is then √2 × d + s.

  距离是那么×√2 d + s。

In code:

在代码:

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