我正在使用 Javascript 构建一个配置工具，它以不同的方式计算电缆中继器的测量值。基本上，您可以输入电缆数量和电缆直径。现在我想将这些电缆可视化为具有给定直径的圆圈，并自动将它们打包在一起以尽可能少地占用空间。这里有两个例子：
7 根电缆打包在一起：
48 根电缆：
如您所见，我已经尝试通过使用物理引擎 ( physics.js ) 来实现这一点，并让重力自动以最佳方式排列元素。这在某种程度上适用于少量元素，但对于大量元素（> 20）需要相当长的时间才能完成，并且并不总是产生最佳结果。除此之外，我认为这种方式有点过头了。
有没有一种简洁的方法来计算x给定直径为d的圆的位置？甚至可能有一个框架或类似的框架来处理这些任务？我很好奇你的想法，在此先感谢。哦，顺便说一句，这不是家庭作业——我 35 岁以上 :-D
如果“尽可能低的空间”是指“包含在最小区域中”（或“被最紧密的凸包包围”），您可能会发现查看Wikipedia 中有关圆形包装的文章很有用：
在二维欧几里得空间中，约瑟夫·路易斯·拉格朗日（Joseph Louis Lagrange）在1773年证明了密度最高的圆的晶格排列是六边形堆积排列，其中圆的中心排列成六边形晶格（交错排列，像蜂窝），每个圆圈被其他 6 个圆圈包围。
你能把你的算法建立在这个发现的基础上吗？我在想的是：从至少覆盖电缆数量的“微不足道”六边形排列开始，然后开始迭代外圈并删除离中心圈最远的那个。继续，直到你得到你需要的确切数量的圆圈。
如果你这样做，你可以节省计算“你已经知道的”的时间。也就是说，如果你有七个圆圈，你就知道它是一个中间有一个圆圈的六边形，句号。如果你有 8 个圆，你从 12 个圆的六边形开始，其中包含 6 个圆的六边形，其中包含 1 个圆：总共 19 个圆（12 + 6 + 1）。您开始从外六边形（有 12 个圆圈的那个）中删除圆圈，直到您删除 11 个，并且您剩下 8 个圆圈（1 + 6 + 1）以最佳排列。
这个算法并不总能找到经过验证的最佳解决方案（这非常困难，因为对于大多数超过 13 的数字来说，最好的配置尚未被证明是理想的），但在大多数情况下，它至少应该给出一个解决方案“相当不错”：
- 从一个中心圆开始并放置它
- 每增加一个圈子
- 在不重叠已经放置的圆的情况下找到最接近中心圆的角度
- 把它放在那里
该算法的时间复杂度取决于您找到新圆的最近位置的效率。通过一些优化，您应该能够使其与圈数成线性关系。这意味着算法的整体复杂度为n².