首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

算法有关问题:圆内随机取点

2013-03-12 
算法问题:圆内随机取点请教个算法问题:在半径为r的圆内随机取n个点,任意两点间距离大于minDistance,其中,n

算法问题:圆内随机取点
请教个算法问题:
在半径为r的圆内随机取n个点,任意两点间距离大于minDistance,
其中,n在区间[3,6]内, r在范围[1.5minDistance, 2*minDistance]内,
圆心为坐标原点
找个o(n)算法,得到一组随机n个点的坐标
[解决办法]
没看懂。。。
[解决办法]
貌似是 Poisson Disk Sampling 的修改版啊,一般算法都是 O(nlogn) 的,见到过一篇 11 年的 paper,其方法理论上是 O(nlogn) 的,不过作者说实测的数据显示基本是个 O(n) 的方法,没仔细读这篇,不知道为啥他们家理论和实测的能反着,楼主有兴趣可以看看,名字叫 Efficient Maximal Poisson-Disk Sampling.

热点排行