查找範圍內的所有點到另一個集合的任意點

我想找到的所有點在乙在一定範圍ř到甲，其中a點b在乙被說成是在範圍之內ř到A內該如果至少有一個點aA其（歐幾里德）距離爲b等於或小於r。這兩組點都是連貫的一組點。它們是從兩個非重疊對象的體素位置生成的。

在1D這個問題相當簡單：內乙 [分鐘（一個） - [R MAX（一個）+ [R]的所有點

但我在3D。

這樣做的最好方法是什麼？

我目前，使用範圍內的一些KNN算法（即MATLAB的rangesearch），然後團結所有這些設置重複搜索的每一個點在一個所有點B中。但我有一種感覺，應該有更好的方式來做到這一點。我更喜歡matlab中的高級別/矢量化解決方案，但僞代碼也可以:)

我還想過將所有點寫入圖像，並在半徑爲r的對象A上使用圖像擴大。但這聽起來像是一個開銷。

來源

2013-08-06 jan-glx

可以使用k-d tree存儲A.所有點

迭代點B B，併爲每一個點 - find the nearest point in A（讓它成爲一）在K-d樹。當且僅當距離d(a,b)小於r時，點b應該包含在結果中。

複雜性將是O(|B| * log(|A|) + |A|*log(|A|))

來源

2013-08-06 17:08:28 amit

謝謝。那正是我所期待的。它將每個案件的運行時間從46秒縮短到10秒。 –

@YAK非常歡迎您，我很高興我可以提供幫助。 – amit

@YAK是否可以共享這樣做的代碼，因爲我真的需要它？ – Tak

bsxfun()這裏是你的朋友。所以，假設你有A中的10分和集合中的3分B。你想讓他們安排，以便單身維度在行/列。我會隨機生成它們的示範

A = rand(10, 1, 3);     % 10 points in x, y, z, singleton in rows 
B = rand(1, 3, 3);      % 3 points in x, y, z, singleton in cols

然後，可以分兩步

dd = bsxfun(@(x,y) (x - y).^2, A, B); % differences of x, y, z in squares 
d = sqrt(sum(dd, 3));     % this completes sqrt(dx^2 + dy^2 + dz^2)

現在可以計算的各點間的距離，你有距離的點之間的陣列一個和B。因此，例如，A中的第3點與B中的第2點之間的距離應該在d(3, 2)中。希望這可以幫助。

來源

2013-08-06 17:22:02 radarhead

感謝您的建議！我也考慮過這個問題，但它隨O（| A | * | B |）縮放，所以我認爲它運行速度較慢。但我會測試和報告。 –

它的確如此。（需要61s）。無論如何，bsxfun對ml用戶來說是非常強大的工具，謝謝你提到它。但準確的，排序和obv。 knnsearch可以提供更高的（因爲算法）加速。 –

@YAK我看到上面的kdtree答案，它很棒。我今天學了些新東西。感謝您的好問題！ – radarhead

我通過先過濾掉乙那肯定是太遠離於一個所有點的點提高@ Amit的解決方案存檔進一步加速，因爲他們太遙遠，即使在一個單一的維度（還挺以下問題中提到的一維解決方案）。

這樣做限制了複雜性O(|B|+min(|B|,(2r/res)^3) * log(|A|) + |A|*log(|A|))其中res是兩個點之間的最小距離，從而降低運行時間在測試情況下，爲5秒（從10秒，並且甚至更在其他情況下）。在MATLAB

示例代碼：

r=5; 
A=randn(10,3); 
B=randn(200,3)+5; 

roughframe=[min(A,[],1)-r;max(A,[],1)+r]; 

sortedout=any(bsxfun(@lt,B,roughframe(1,:)),2)|any(bsxfun(@gt,B,roughframe(2,:)),2); 
B=B(~sortedout,:); 
[~,dist]=knnsearch(A,B); 
B=B(dist<=r,:);

來源

2013-08-06 21:18:13

查找範圍內的所有點到另一個集合的任意點

回答

相關問題