[問題] 平面上 N 點，放額外一點 P 求最近點
看板Prob_Solve (計算數學 Problem Solving)作者EdisonX (卡卡獸)時間10年前 (2014/10/30 21:00)推噓5(5推 0噓 16→)留言21則, 7人參與討論串1/1
變數假設
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://www.ptt.cc/bbs/Prob_Solve/M.1414674032.A.1D6.html
→
10/30 21:02, , 1F
10/30 21:02, 1F
這算法是找 b[n] 裡的最近兩點不是嗎？
但我想找的 "比較像 (但似乎不完全是)" 是，
給定一點 c , 求 c 與 b[n] 裡最近的一點，
還是這問題一樣可以從 最小點對 (closest pair) 問題轉過來？
謝謝您的回答。
※ 編輯: EdisonX (180.177.74.8), 10/30/2014 21:09:39
推
10/30 21:06, , 2F
10/30 21:06, 2F
→
10/30 21:28, , 3F
10/30 21:28, 3F
→
10/30 21:29, , 4F
10/30 21:29, 4F
推
10/31 04:27, , 5F
10/31 04:27, 5F
→
10/31 09:09, , 6F
10/31 09:09, 6F
→
10/31 09:11, , 7F
10/31 09:11, 7F
→
10/31 09:11, , 8F
10/31 09:11, 8F
→
10/31 09:28, , 9F
10/31 09:28, 9F
→
10/31 09:29, , 10F
10/31 09:29, 10F
今天抽時間稍試了下，kd-tree, 在 asize = bsize = 40M , dim==2 的情況下，
雖然比暴力法很好多，
似乎還是要花費不少時間 , 我試著去優化 code , 節省還是有限 .
不知道有沒有人對這議題有所研究可再提供點方向？
謝謝各位。
※ 編輯: EdisonX (180.177.74.8), 10/31/2014 21:28:35
→
11/01 00:28, , 11F
11/01 00:28, 11F
推
11/01 06:07, , 12F
11/01 06:07, 12F
→
11/01 06:08, , 13F
11/01 06:08, 13F
推
11/01 07:39, , 14F
11/01 07:39, 14F
→
11/01 07:41, , 15F
11/01 07:41, 15F
→
11/01 07:42, , 16F
11/01 07:42, 16F
→
11/01 07:51, , 17F
11/01 07:51, 17F
→
11/01 22:31, , 18F
11/01 22:31, 18F
→
11/01 22:32, , 19F
11/01 22:32, 19F
先說下吧，我用的是 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
推
11/04 03:25, , 20F
11/04 03:25, 20F
→
11/04 03:25, , 21F
11/04 03:25, 21F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
