PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Prob_Solve
[问题] 平面上 N 点,放额外一点 P 求最近点
楼主:
EdisonX
(卡卡兽)
2014-10-30 21:00:26
变量假设
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 ?
先谢谢各位。
作者:
bibo9901
(function(){})()
2014-10-30 21:02:00
closest pair problem
作者:
FRAXIS
(喔喔)
2014-10-30 21:06:00
nearest neighbor query
楼主:
EdisonX
(卡卡兽)
2014-10-30 21:28:00
疑!想一下也像是 knn(k==1) , 实作上似乎麻烦多 Orz谢谢 FRAXIS , 我再搜一下有什么算法解这问题 , 感谢
作者:
m80126colin
(许胖)
2014-10-31 04:27:00
有个东西叫做 Voronoi Diagram,不知道有没有相关?
作者:
scwg
( )
2014-10-31 09:09:00
http://stackoverflow.com/questions/5077318/
是你要的吗? 还是你要 min_dist/idx forall a?kd-tree for b should help anyway
楼主:
EdisonX
(卡卡兽)
2014-10-31 09:28:00
@scwg , 嗯 , 我要的是 min_dist/idx forall a? , 谢谢提供的 keyword , 感谢。
作者:
LPH66
(-6.2598534e+18f)
2014-11-01 00:28:00
kd-tree 主要是查询省时间, 点集固定查询点很多时很有用
作者:
FRAXIS
(喔喔)
2014-11-01 06:07:00
因为你的b是静态的 先建Voronoi diagram然后建立point location的查询 应该会比较快
作者:
DJWS
(...)
2014-11-01 07:39:00
scholar.google.com.tw/scholar?&q=nearest+neighbor+querybooks.google.com.tw/books?&q=nearest+neighbor+query这个题目有成千上万人做过 方向很多比较浅显易懂的介绍
http://www.cs.uu.nl/geobook/
楼主:
EdisonX
(卡卡兽)
2014-11-01 22:31:00
明天我整理下目前所做的 code 放上来 , 先谢谢各位给的资讯,真的非常感谢!
作者:
FRAXIS
(喔喔)
2014-11-04 03:25:00
Kd-Tree是支援dynamic insert/delete的你的问题中b是静态的 所以要找static data structure
继续阅读
[问题] Sorting in O(n)...
shaopin
[问题] selection problem
jb679123
[问题] 不重叠的圆求最大面积
jjwang
[问题] 时间复杂度
qwerty147852
Re: [问题] 给定n个排好序的整数阵列 找中位数
FRAXIS
Re: [问题] 给定n个排好序的整数阵列 找中位数
DJWS
Re: [问题] 给定n个排好序的整数阵列 找中位数
chz
Re: [问题] 给定n个排好序的整数阵列 找中位数
dreamoon
Re: [问题] 给定n个排好序的整数阵列 找中位数
DJWS
Re: [问题] 给定n个排好序的整数阵列 找中位数
FRAXIS
Links
booklink
Contact Us: admin [ a t ] ucptt.com