作者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/cn.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