返回信息流最近遇到一个问题，在一个图形（六边形）内随机撒多个半径为R的圆（半径固定所以只随机生成圆心坐标即可），但要求他们不相交~~~该怎么处理呢？
依次判断与之前撒好的圆心距离感觉有点低效呀。。。我觉得应该是有种解法，每次撒了一个新的圆后，在图形中抠掉这块，这样下一个要撒的圆的圆心坐标就有一定的限制了。。。
不知道C++有没有这样的算法。。或者更高效的算法求各位大大解救！~~~~[ema1][ema1]
这是一条镜像帖。来源：北邮人论坛 / cpp / #96886同步于 2017/11/22
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
小白求问 如何在一个图形内快速撒出多个不相交的圆
Mouclltzahd
2017/11/22镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
我觉得需要看需求。
1. 如果不要求精确的话，就先分割成边长为R的小方格，再从中抽取，再考虑边界和碰撞等。类似于游戏中碰撞检测的机制。但是问题就是边界周围被选中概率很可能会提高一点，已有圆的周围被选中概率可能会下降一点。
2. 如果要求精确的话，就是无限随机直到成功生成或者尝试次数上限吧
while(!success && count < upper_bound){
generate_rand_x_and_y();
count++;
if(in 六边形){
if(!collide with ohters in existing set){
success = add_to_set();
}
}
}
这种情况下也可以利用上面的思想，先把圆分块，简单排除大部分，然后只精确计算来检测高危区域的圆。但仍然有一定概率会GG就是了。
同时也有可能不可能放得下那么多圆，这种情况就需要想想是否需要处理和怎么处理了。
是这样的 但是剩余区域的坐标怎么数学表示？再撒新的圆的时候限制条件需要一个数学上的公式
【 在 chenxiansf 的大作中提到: 】
: 每次抠掉半径为2R的圆？
嗯嗯好全面～思路确实是这样的…但是如果撒出来再去根据两点距离公式判断是否可用效率太低啦……更好的办法是确定好一个圆了 就把圆抠掉 下次在新的区域内随机确定圆心坐标。 but怎么表示这个区域呢……
【 在 bond1993 的大作中提到: 】
: 我觉得需要看需求。
: 1. 如果不要求精确的话，就先分割成边长为R的小方格，再从中抽取，再考虑边界和碰撞等。类似于游戏中碰撞检测的机制。但是问题就是边界周围被选中概率很可能会提高一点，已有圆的周围被选中概率可能会下降一点。
: 2. 如果要求精确的话，就是无限随机直到成功生成或者尝试次数上限吧
请问一下你是什么专业的？
一般可以想到的“扣掉这个区域”的做法就是记录已存在的圆的（大致/精确）位置然后判断。
【 在 Mouclltzahd 的大作中提到: 】
: 嗯嗯好全面～思路确实是这样的…但是如果撒出来再去根据两点距离公式判断是否可用效率太低啦……更好的办法是确定好一个圆了 就把圆抠掉 下次在新的区域内随机确定圆心坐标。 but怎么表示这个区域呢……