從列表中獲取3個最常見的點<Point>

我有一個快速問題，我沒有找到如何有效地做（在C＃中）。我有一個點（X，Y）列表數組。我需要找出哪3個點是最緊密的聚類。這是一個測繪項目。從列表中獲取3個最常見的點<Point>

什麼會做的最好的方式是這樣？列表中只有6到9個項目。

在此先感謝。

乾杯！

來源

2011-11-08 kodikas

什麼是「緊集羣」？ –

謝謝！我決定只是採取暴力手段。歡呼和感謝您的建議。 – kodikas

@PetarMinchev緊密集羣 - 我的意思是3點距離彼此最近。 – kodikas

對於這樣的小數字，蠻力方法應該工作得很好。有六點，三點有20種可能的組合。有9分，有84種可能的組合。我不會在很多方面推薦這種方法，但只有少數幾個方面，它會足夠快，寫起來很簡單。

您可以輕鬆地生成組合：如果您創建這些結構爲每個組中的一個，並將其存儲在

struct PointGroup 
{ 
    public readonly int i; 
    public readonly int j; 
    public readonly int k; 
    public readonly double tightness; 
    public PointGroup(int i, int j, int k, double tight) 
    { 
     this.i = i; 
     this.j = j; 
     this.k = k; 
     this.tightness = tight; 
    } 
}

：

for (int i = 0; i < points.Length - 2; ++i) 
{ 
    for (j = i + 1; j < points.Length - 1; j++) 
    { 
     for (k = j + 1; k < points.Length; k++) 
     { 
      // Here, your three points are 
      // points[i], points[j], and points[k] 
      // compute "tightness" and store 
     } 
    } 
}

你需要一個結構來保存你的組合一個數組，你可以簡單地對數組進行排序，並採取最好的三個。

你的大問題是想出一個「緊團」的定義。此外，你必須決定一個點是否可以在多個「最緊密」的組中。定義氣密度的三種可能方法是：

點之間的距離總和最小。
從每個點到組中心的平均距離被最小化。
由三點形成的三角形的圓周被最小化。

毫無疑問，還有更多。

來源

2011-11-08 18:46:45

謝謝！乾杯! – kodikas

可以按如下方式簡化問題：

不要檢查點自相;距離爲零。
漏洞利用對稱性：距離點i到點j是相同點j的點I

那些消除多種組合。

但是，鑑於這些，你必須計算每對之間的距離並進行排序。

來源

2011-11-08 18:24:06 duffymo

如果點不相同，則這將成爲cluster analysis的一種形式。

存在各種不同的算法，它們在測量和「聚類」點方面有所不同，儘管只有幾個點，蠻力方法可能是最簡單的方法......您可以測量每對點之間的距離，並排序...

來源

2011-11-08 18:24:55

從列表中獲取3個最常見的點<Point>

回答

相關問題