网格上两点之间距离的快速算法？

Question

给定一个宽度乘以长度（例如 5 x 4）的网格和该网格上点的 X 和 Y 坐标数组，打印网格上每个点到坐标的距离，如下所示：

宽度=5

len = 4

x 坐标 = (2,4)

y 坐标 = (2,3)

一手"across"为+2，纵横手为+1

假设 xCoords.length = yCoords.length

稍后我会post我的解决方案，或者更确切地说是尝试解决方案。我在尝试想出一个函数来将网格坐标 (i,j) 的距离转换为点的坐标时遇到了困难...所以基本上

for i .. width
  for j .. length
    getDistance(i,j, xCoords,yCoords)

(0,0) (0,1) (0,2) (0,3)

(1,0) (1,1) (1,2) (1,3)

(2,0) (2,1) (2,2) (2,3)

等...

到这些坐标处的实际距离值。

Answer 1

您想使用勾股定理。 sqrt((i-xCords)*(i-xCords)+(j-yCords)*(j-yCords))

Answer 2

int getDistance(int x1, int y1, int x2, int y2) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

Answer 3

相关：I want to calculate the distance between two points in Java

距离 = Math.sqrt( Math.pow((i-xCords), 2) + Math.pow((j-yCords), 2));

Answer 4

我假设您正在寻找到向量中给出的距离中最近的 coord 的距离，即

for i 0 .. width
    for j 0 .. length
        best = distance(i, j, coords[0].x, coords[0].y)
        for k 1 .. coordVector // Skip first element
            best = min(best, distance(i, j, coords[k].x, coords[k].y)
        result[i][j] = best

第三个嵌套循环检查给定坐标到向量中所有坐标的距离(x_i, y_i), 挑出最短的一个，存入变量best。请注意，best 是用到向量中第一个点的距离初始化的，因此嵌套循环从第二个点开始。

您现在只需要一个 distance 的计算器。根据问题描述，你要找 Manhattan Distance 因为对角线一步的权重为 2，这意味着它与水平一步加垂直一步相同：

distance(x0, y0, x1, y1)
    horizontal = abs(x1-x0)
    vertical = abs(y0-y1)
    return horizontal + vertical

网格上两点之间距离的快速算法？

Quick algorithm for distance between 2 points on a grid?

java

distance

solver