從座標列表的最小距離查找座標

我有一個2D空間座標列表（x _i，y _i）。我如何找到座標（X，Y），使其與其他給定座標之間的距離最小？是否有解決（X，Y）的數學公式？從座標列表的最小距離查找座標

讓我舉個例子.. 可以說我有co.ordinates（0,0）;（1,0）;（0,1）;（ - 1,0）;（0， - 1）; 現在我必須找出可能的co.ordinate（s）（一個或多個），使得生成的co.ordinate與所有點的距離最小。在這種情況下（0,0）。

正如VOO說，這是我的要求： 查找距離的和最小的點中的一個點一組給定

來源

2012-05-09 Jeevi

@Voo意味着所有的Y均：哦，是的，這是可能的。 OP沒有提到「總和」，但我認爲你可能是對的。讓我們希望他們澄清... –

TFool，請澄清你到底在找什麼。 –

@Oli我認爲我們應該停止刪除帖子/評論，否則這會變得相當複雜;）（我不會刪除你的回答，畢竟這是一個可能的解釋的好回答）總結對話：有兩種方法可以解釋問題：找出給定集合中與給定點具有最小距離的點。或者：找到一個最小化到給定集合中點的距離總和的點。 – Voo

可以使用euclidien距離公式兩點之間的距離計算：平方根（（x1-X）2 +（yi-Y）2）或者可以使用曼哈頓公式： | yi-Y | + | xi-X |。

這是一個尋路問題？

來源

2012-05-09 13:42:41 Anila

假設你要求的最近的候選給定點

你問nearest neighbour searches。

最簡單的方法是簡單地遍歷每個候選座標，計算歐幾里得距離（假設您需要歐幾里得度量）並跟蹤最小值。這足夠嗎？

更復雜（但可能更快）的方法涉及將候選點存儲在例如例如space-partitioning tree，例如四叉樹或kd樹，或其他幾種變體之一。

來源

2012-05-09 13:43:42

public Coord2D minDistance(List<Coord2D> coordinates, Coord2D someCoord) { 
    float minDistance = Float.MAX_VALUE; 
    Coord2D result; 
    for (Coord2D coord : coordinates) { 
     float distance = Math.sqrt(Math.pow((coord.x - someCoord.x), 2) + (Math.pow((coord.y - someCoord.y), 2)) 
     if (distance < result) { 
      result = coord; 
      minDistance = distance; 
     } 
    } 

    return result; 
}

來源

2012-05-09 13:45:08 giorashc

如果列表很大，那麼你可以通過只做一個循環外的單個sqrt。 –

@DavidHeffernan你的意思是對某些矩陣的功率計算（sqrt必須按每個座標計算） – giorashc

不，由於sqrt是單調的，所以f（x）最小化的點也使f（x）^ 2最小化，所以你可以推遲sqrt到最後。 –

要求：找到一個點，最小化給定集合中點的距離之和。

具有最小歐幾里德距離之和所有其他點的點，具有：

X =意味着所有的X的平均集合中的
Y =該組中

來源

2012-05-24 14:37:30 deuce

從座標列表的最小距離查找座標

回答

相關問題