我需要计算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点之间的网格距离
发布评论