计算2点之间的网格距离

本文介绍了计算2点之间的网格距离的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要计算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; }