發現三個最近的點

Question

我點的座標平面的列表，以及一個測試點。我想找到離測試點最近的三個點的列表索引。有什麼更好的方法來找到這些指數？預先感謝旅遊回覆。

===編輯===

我在C++中找到了一個解決方案。起初，我創建了一個向量：

typedef struct 
{ 
    int iIndex; 
    double dSqrDistance; 
} IndexedDistance; 

std::vector<IndexedDistance> xDistanceVector; 

，然後一個功能它的元素

bool compareIndexedDistance(IndexedDistance xD1, IndexedDistance xD2) 
{ 
    return (xD1.dSqrDistance < xD2.dSqrDistance); 
} 

然後在一個循環中我計算所有的距離，然後我對它們進行排序分類，並在最後我拿前三元素：

IndexedDistance xDistanceElement; 
for (int i = 0; i < xPointList.size(); i++) 
{ 
    dSqrDistance = xPointList.at(i).sqrDistance(xTestPoint); 
    xDistanceElement.iIndex = i; 
    xDistanceElement.dSqrDistance = dSqrDistance; 
    xDistanceVector.push_back(xDistanceElement); 
} 

std::sort(xDistanceVector.begin(), xDistanceVector.end(), compareIndexedDistance); 
xDistanceVector.resize(3); 

就這樣，我找到了我所需要的。我不知道這是不是最好的方法，但它似乎工作。

Answer 1

二進制空間分割可提供的算法複雜度O（日誌的n * log n）的。

1. 確定您的點集的邊界。 Infinum和確界點會給你包含集中的所有點軸對齊方。
2. 分成兩邊界正方形通過任何軸。爲每個方塊製作一個包含點的單獨列表。將每個邊界方塊鏈接到父方塊。
3. 重複分割邊界平方（步驟2），直到相應的含點的列表將是相當小的，以利用窮舉搜索。

現在您將可以使用樹狀搜索來定位感興趣點周圍的空間，從而大大減少距離測試的次數。

棘手的部分是，您必須掃描所有鄰居圍繞感興趣點的邊界方塊，因爲最近的點可能在其中任何一個位置。