如何在N點中間找到一個點？

Question

假設我有N個點由它們的座標（X，Y）定義。我怎麼能找到另一個點X的座標，這個點在這N個點的中間（即X與每個點之間的距離N大致相等）。有沒有什麼算法可以做到這一點？

Answer 1

有可能沒有這樣的觀點。你可以對X和Y進行平均，得到一個位於中間的點（又名「質心」）。

Answer 2

對於2分這個「中」存在。對於更多我們不能確定。

您可以用點的X和y的平均值計算質心。

if (points.lenght > 0) { 
 
    var x_acc = 0; 
 
    var y_acc = 0; 
 

 
    for (int i = 0; i < points.length; i++) { 
 
    x_acc += points[i].x; 
 
    y_acc += points[i].y; 
 
    } 
 

 
    var x_centroid = x_acc/points.lenght 
 
    var y_centroid = y_acc/points.lenght 
 
}

Answer 3

你可能被認爲「在中間」點等距於所有其他錯誤陳述的問題。

如果你無法做到這一點，一個更好的方法是儘量減少中心到N點的總歐幾里得距離。

事實證明，這個問題沒有簡單的解析解，因爲你需要儘量減少

D = Σ √(X - Xc)² + (Y - Yc)² 

得出關於XC，你

D'x = Σ (X - Xc)/√(X - Xc)² + (Y - Yc)² = 0 

一個複雜的非線性表達。這個問題被稱爲「幾何中位數」，你會發現更多信息here（尤其是Weiszfeld算法）。

在相反，最小化的平方和的距離

D = Σ (X - Xc)² + (Y - Yc)² 

是微不足道

D'x = 2 Σ (X - Xc) = 0 

其產生質心。

Xc = Σ X/N, Yc = Σ Y/N. 

---

你也可以認爲你的觀點，這是從給定的距離，別人的和最小的點medoid的。需要N(N-1)/2距離計算才能找到它。