網格上2點之間距離的快速算法？

-1

給定一個網格的長度（如5 x 4）寬度和該網格上點的X和Y座標陣列，打印網格上每個點與座標的距離如下：網格上2點之間距離的快速算法？

width = 5

LEN = 4

X COORDS =（2,4）

ŷCOORDS =（2,3）

甲移動「橫跨」是+ 2，垂直或水平移動是+1

假設xCoords.length = yCoords.length

我稍後會發布我的解決方案，或者說在一個解決方案的嘗試。我被困試圖拿出一個功能轉由網格座標（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）

etc ...

到這些座標的實際距離值。

來源

2016-06-20 sloven

您是否在尋找[勾股定理（HTTPS ：//en.wikipedia.org/wiki/Pythagorean_theorem）？ – Gendarme

不，我的意思是，我知道它是什麼，我只是不確定它是如何適合這裏的？我如何計算從（i，j）到xCoords/yCoords座標的距離？我不知道如何做到這一步 – sloven

從左下角到上角的最短路線是斜邊。如果您有兩個角的座標，則可以計算斜邊，從而計算最短路線（距離）。 – Gendarme

我假設你正在尋找在矢量給出的那些中最近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 _我，Y _我），挑選在可變best最短的一個，並將其存儲。請注意，best初始化的距離爲向量中的第一個點，所以嵌套循環以第二個點開始。

現在您只需要一個計算器distance。根據問題的描述，您正在尋找Manhattan Distance因爲對角線步加權爲2，這意味着它一樣一步水平加一步垂直：

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

來源

2016-06-20 15:16:07 dasblinkenlight

非常感謝，這是我正在尋找的答案！ – sloven

有一點需要注意，每次你爲零索引網格調用距離時，你需要爲i，j做+ 1，所以實際上函數調用將如下所示：distance（i + 1，j + 1，coords [0]）。 x，coords [0] .y） – sloven

@Nik這是正確的，在將這個僞代碼轉換爲Java程序時，需要解決座標轉換問題。 – dasblinkenlight

你想使用畢達哥拉斯定理。 sqrt((i-xCords)*(i-xCords)+(j-yCords)*(j-yCords))

來源

2016-06-20 15:11:40 Joopkins

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

來源

2016-06-20 15:12:52 4castle

'Math.pow（（x1 - x2）* 2，2）'爲什麼你乘以2？ – Gendarme

@Gendarme這個問題說「accross」實際上是單位2. – 4castle

好吧，陷阱。 – Gendarme

距離= Math.sqrt（Math.pow（第（i-xCords），2）+ Math.pow（（J-yCords），2））;

來源

2016-06-20 15:13:59 vathek

網格上2點之間距離的快速算法？

回答

相關問題