作者EdisonX (卡卡獸)
站內Prob_Solve
標題[問題] 平面上 N 點，放額外一點 P 求最近點
時間Thu Oct 30 21:00:26 2014
變數假設
struct Point { float x , y ; }
Point a[m];
Point b[n];
最大點對 問題是在 a 裡面，找最近的兩點 ，
( ↑雖然這我也不會有效的方法 )
但我的問題是，把 a[i] 依序放入 b 中，
從 b 裡找出與 a[i] 最近的點，
暴力法用虛碼表示如下
for(i = 0 : m-1 )
{
min_idx = 0 ;
min_dist = distance( a[i], b[min_idx] );
for(j = 1 : n-1)
{
dist = distance( a[i] , b[j] ) ;
if ( dist < min_dist)
{
min_dist = dist ;
min_idx = j;
}
}
// min_dist , min_idx 是要求的 , 到時候會全部存下來
}
想請教是否有什麼算法可較快完成上述需求？
或我該找什麼 keyword ?
先謝謝各位。
--
「自從我學了 C# , 人都變聰明 , 考試都考一百分」
「自從我學了 VB , 皮膚都變好 , 人也變漂亮了 」
「自從我學了 Java , 明顯變壯 , 個子也變高了 」
「自從我學了 C++ , 內分泌失調 , 頭都禿了... 」
< Kuso 星爺語錄 >
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.74.8
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1414674032.A.1D6.html
1F：→ bibo9901: closest pair problem 10/30 21:02
這算法是找 b[n] 裡的最近兩點不是嗎？
但我想找的 "比較像 (但似乎不完全是)" 是，
給定一點 c , 求 c 與 b[n] 裡最近的一點，
還是這問題一樣可以從 最小點對 (closest pair) 問題轉過來？
謝謝您的回答。
※ 編輯: EdisonX (180.177.74.8), 10/30/2014 21:09:39
2F：推 FRAXIS: nearest neighbor query 10/30 21:06
3F：→ EdisonX: 疑！想一下也像是 knn(k==1) , 實作上似乎麻煩多 Orz 10/30 21:28
4F：→ EdisonX: 謝謝 FRAXIS , 我再搜一下有什麼算法解這問題 , 感謝 10/30 21:29
5F：推 m80126colin: 有個東西叫做 Voronoi Diagram，不知道有沒有相關？ 10/31 04:27
7F：→ scwg: 是你要的嗎? 還是你要 min_dist/idx forall a? 10/31 09:11
8F：→ scwg: kd-tree for b should help anyway 10/31 09:11
9F：→ EdisonX: @scwg , 嗯 , 我要的是 min_dist/idx forall a? , 謝謝 10/31 09:28
10F：→ EdisonX: 提供的 keyword , 感謝。 10/31 09:29
今天抽時間稍試了下，kd-tree, 在 asize = bsize = 40M , dim==2 的情況下，
雖然比暴力法很好多，
似乎還是要花費不少時間 , 我試著去優化 code , 節省還是有限 .
不知道有沒有人對這議題有所研究可再提供點方向？
謝謝各位。
※ 編輯: EdisonX (180.177.74.8), 10/31/2014 21:28:35
11F：→ LPH66: kd-tree 主要是查詢省時間, 點集固定查詢點很多時很有用 11/01 00:28
12F：推 FRAXIS: 因為你的b是靜態的 先建Voronoi diagram 11/01 06:07
13F：→ FRAXIS: 然後建立point location的查詢 應該會比較快 11/01 06:08
14F：推 DJWS: scholar.google.com.tw/scholar?&q=nearest+neighbor+query 11/01 07:39
15F：→ DJWS: books.google.com.tw/books?&q=nearest+neighbor+query 11/01 07:41
16F：→ DJWS: 這個題目有成千上萬人做過 方向很多 11/01 07:42
18F：→ EdisonX: 明天我整理下目前所做的 code 放上來 , 先謝謝各位給的 11/01 22:31
19F：→ EdisonX: 資訊，真的非常感謝！ 11/01 22:32
先說下吧，我用的是
http://rosettacode.org/wiki/K-d_tree
這網頁的 code 抓下來改，
整個順序如同 FRAXIS , LPH66 所言，一堆 b 事先做 make_tree 後，
再逐一將每個 a 點丟到 nearest 做查詢，
效能上是比暴力法提升了一百多倍，唯需求上盡可能還需再快，
想請教這效能是否已是上限？
若說明不夠，需再放我手上版本的 code , 我可再附上。
謝謝各位。
※ 編輯: EdisonX (180.177.74.8), 11/03/2014 23:55:21
20F：推 FRAXIS: Kd-Tree是支援dynamic insert/delete的 11/04 03:25
21F：→ FRAXIS: 你的問題中b是靜態的 所以要找static data structure 11/04 03:25