如何找到一組點中第k個點的最近鄰點

我在2d平面上有一組點（x，y）。給定一個點（x0，y0）和數k，如何找到點集中（x0，x0）的第k個最近鄰點。詳細地說，點集由兩個數組表示：x和y。點（x0，y0）由索引i0給出。它意味着x0 = x（i0）和y0 = y（i0）。如何找到一組點中第k個點的最近鄰點

是否有任何功能或Matlab的東西可以幫助我解決這個問題。如果Matlab沒有這樣的功能，你能否提出其他有效的方法。

編輯：我必須爲集合中的每個點（x0，y0）計算這種距離。該集合的大小約爲1000. k的值應大約爲sqrt（1500）。最糟糕的是我做了很多次。在每次迭代中，設置發生變化，然後再次計算距離。所以，運行時間是一個關鍵問題。

來源

2012-02-22 James Do

，如果你會做這種檢查對於很多點，你可能要構建一個點間距離表第一

squareform(pdist([x y]))

來源

2012-02-23 01:47:43 zamazalotta

是的。我會爲這組中的每一點做到這一點。所以，某種距離表有助於節省運行時間。我將發現squareform函數在我的問題中如何工作。非常感謝你。 – 2012-02-23 03:34:39

其實函數是pdist，squareform只是使pdist的向量輸出 – zamazalotta 2012-02-23 06:51:19

出一個方陣，謝謝zamazalotta。我知道了。 – 2012-02-23 07:24:55

如果您有統計工具箱，則可以使用功能knnsearch。

來源

2012-02-22 21:57:39 3lectrologos

knnsearch似乎是一個解決辦法，但我不知道如何knnsearch應用到我的問題確切。我會找到它。無論如何，你能給我更多關於使用knnsearch的方式的細節。非常感謝你。 – 2012-02-23 03:30:37

你看過Matlab的幫助（添加到我的答案上面的鏈接）？ – 3lectrologos 2012-02-23 16:58:21

我閱讀了關於knnsearch的在線文檔，但對我來說有點複雜，而且我沒有太多時間來理解和使用它。我嘗試了更簡單的方法。它需要更多時間跑步，但我會先嚐試這種方法。感謝您的幫助。 – 2012-02-23 17:37:59

蠻力算法是這樣的：

array x[n] =() 
array y[n] =() 
array d[n] =() 

... populate x and y arrays with your n points ... 

/* step over each point and calculate its distance from (x0, y0) */ 
for i = 1 to n 
do 
    d[i] = distance((x0, y0), (x[i], y[i]) 
end 

/* sort the distances in increasing order */ 
sort(d) 

/* the k'th element of d, is the k'th nearest point to (x0, y0) */ 
return d[k]

來源

2012-02-22 21:59:32 ardnew

感謝您的幫助！ – 2012-02-23 03:27:03

蠻力方法看起來是這樣的：

%Create some points 
n = 10; 
x = randn(n,1); 
y = randn(n,1); 

%Choose x0 
ix0 = randi(n); 

%Get distances 
d = sqrt(... 
    (x - x(ix0)).^2 + ... 
    (y - y(ix0)).^2); 

%Sort distances 
[sorted_Dstances, ixSort] = sort(d); 

%Get kth point 
k = 3; 
kth = [x(ixSort(k+1)); y(ixSort(k+1))]; %+1 since the first element will always be the x0 element.

來源

2012-02-22 22:00:28 Pursuit

不應該刪除元素本身？考慮一下案例k = 1 – 2012-02-22 22:26:19

好點。我通常不喜歡像這樣改變匹配向量的大小。也許給最終索引添加一個'+1'。編輯：雖然如果有一個點與初始點相同，那麼會留下一個空白。如果你想保證答案是一個不同的觀點，即使有些觀點可能是平等的，那麼也需要做更多的工作。 – Pursuit 2012-02-23 00:50:49

@追求它也沒有意義也刪除相同的點。如果你有5個相同的點，你搜索的點，第3個最遠的距離應該是0 – ardnew 2012-02-23 02:20:49

自由和開源VLFeat工具箱包含一個kd樹實現，以及其他有用的東西。

來源

2012-02-22 22:34:56 Maurits

非常感謝。我會找到它是否可以幫助。 – 2012-02-23 03:37:14

如何找到一組點中第k個點的最近鄰點

回答

相關問題