algorithm - 在正方形中随机分布圆的算法的想法

Question

我正在寻找一个概念，可以在正方形中随机分布圆圈，这样它们就不会重叠。所有圆圈的大小都相同。圆圈覆盖的面积可能很高，最高可达 ca 的理论最大值。 90% 的正方形(它们在其中完全有序)。应该放置大约 200 个圆，我想准确指定圆的数量。 (需要将分布作为有限元分析模型生成的输入，顺便说一句)

使用在空闲点上按顺序放置圆圈的直接算法，覆盖范围不可能超过 54%，这不足为奇，因为在某些时候根本没有剩余空间。因此，以前的 SO 线程并没有真正解决我的问题(接近:Placing random circles without overlap (and without using brute force)?)

通过对一组有序圆的圆进行简单的随机位移，分布似乎“不够随机”。

到目前为止，我提出的所有概念都感觉过于复杂或蛮力风格。我最喜欢的方法是确定可以放置下一个圆圈的所有可能位置，以便剩余空间足够大以放置剩余的圆圈。然后随机选择这些位置之一，依此类推。但是:要确定剩余空间的“容量”并不容易，而且在数值上非常复杂。我真的不知道该怎么做，也不知道是否可以通过合理的数值努力来完成。

第二个想法是台球模拟:将所有圆圈以任意模式放置并模拟大台球台球。相当蛮力，而且在数字上也非常昂贵。我也有点害怕离散化问题。

数字 3 更具数学性，它基于为每个圆定义一个具有随机“强度”的势场，以便圆之间存在某种引力并计算平衡状态。为此开发数学模型并非易事，将是一项艰巨的任务...

那么 - 最后 - 问题:您对尽可能轻量级地解决问题有何建议？你知道我应该考虑解决这个问题的算法吗？您对我的想法有何评论？

提前谢谢大家!很高兴看到您的回答。

Answer 1

首先使用 basic algorithm绘制尽可能多的不碰撞的圆圈。当它完成时(它不能达到 200 圈)，开始推圈。我的意思是用物理引擎将它们物理地插入: http://www.sgtconker.com/2010/09/article-xna-farseer-platform-physics-tutorial/ (不使用重力)。