空间填充不等大小的圆圈

这是我的问题：

• 我需要在canvas中显示一堆圆圈。
• 存在任意数量的圆，每个圆具有预定义的半径。
• 圆的总面积始终小于canvas的面积。

我想定位圆圈，使它们占据canvas内可用的最大空间，而不会相互接触。 我的目标是实现视觉上令人愉悦的效果，其中圆圈在canvas内分布均匀。 我不知道这是否真的是“空间填充”，因为我的目标不是最小化元素之间的距离，而是最大化它。

这是我想要实现的一个例子：

我的第一个“蛮力”想法如下：

1. 对于每个圆圈：计算其边界与每个圆圈边界之间的最短距离; 总结所有这些距离，称之为X.
2. 计算所有X的总和。
3. 随机更改圆圈之间的距离。
4. 重做1-3以进行预设的迭代次数并获取在步骤（2）获得的最大值。

然而，这似乎并不优雅; 我确信有更好的方法来做到这一点。 有没有现成的算法来实现这样的布局？ 我可以使用任何现有的库（JavaScript或Ruby）来实现这一目标吗？

编辑

这是接受答案的Javascript版本 ，它使用Raphael绘制圆圈。

Answer 1

我会尝试在球体之后插入球体（最大的第一个）。 每个都添加在最大可用空间中，具有一些随机抖动。

查找（或多或少）最大可用空间的一种相对简单的方法是想象视图上的点网格，并为每个网格点（在2D数组中）存储距离任何项目的最近距离：边缘或球体，以较小者为准是最接近的。 添加每个新球体时，将更新此数组。

要添加新球体，只需获取最远距离的网格点并应用一些随机抖动（实际上您知道可以抖动多少，因为您知道距离最近项目的距离）。 （我将随机化不超过（dr）/ 2，其中d是数组中的距离，r是要添加的球体的半径。

添加另一个圆后更新此数组并不是火箭科学：您为每个网格点计算新添加的球体的距离，如果更大，则替换存储的值。

您的网格可能太粗糙，并且您无法再添加圆圈（当2Darrays不包含大于要添加的圆的半径的距离时）。 然后你必须在继续之前增加（例如加倍）网格分辨率。

以下是此实现的一些结果（它花了我大约100行代码）

• 100个不同大小的圆圈

• 500个不同大小的圆圈

• 100个相同大小的圆圈

这里有一些粗略的C ++代码（只是算法，不要指望这个编译）

// INITIALIZATION // Dimension of canvas float width = 768; float height = 1004; // The algorithm creates a grid on the canvas float gridSize=10; int gridColumns, gridRows; float *dist; void initDistances() { // Determine grid dimensions and allocate array gridColumns = width/gridSize; gridRows = height/gridSize; // We store a 2D array as a 1D array: dist = new float[ gridColumns * gridRows ]; // Init dist array with shortest distances to the edges float y = gridSize/2.0; for (int row=0; rowdistanceFromLeft) dist[i] = distanceFromLeft; if (dist[i]>distanceFromRight) dist[i] = distanceFromRight; } x+=gridSize; } } void drawCircles() { for (int circle = 0; circled) dist[i] = d; // Optimized implementation (no unnecessary sqrt) float prev2 = dist[i]+radius; prev2 *= prev2; if (prev2 > d2) { float d = sqrt(d2) - radius; if (dist[i]>d) dist[i] = d; } xx += gridSize; i++; } yy += gridSize; } } } 

Answer 2

也许一些力导向布局的应用会很有用。

Answer 3

既然你的目标只是“达到令人愉悦的效果”，而不是解决数学问题，你应该尝试最简单的算法，它可以先工作，看看它是否好看。 应该没有必要使用非常复杂的数学。

我知道你希望球体“填充”可用空间，而不是在其他区域拥挤的情况下留下大的空白区域。 您还希望布局显示为随机 – 不排列在网格上或类似的东西上。

实现这一目标的明显，简单的方法就是将球体逐个放置在随机位置。 如果一个人落在已放置的球体之上，则生成另一个随机位置，直到找到一个适合的位置。

看来图像中大约有40个球体。 40个球体全部落在图像的同一区域，其余部分空白的可能性非常非常小。 随着球体数量的增加，获得非常不平衡布局的可能性将接近于零。

先尝试一下，看看它是否符合您的需求。 如果它不够“均匀”，你应该能够使用一些非常简单的数学来偏向随机选择的位置，而选择空白区域。 不应该使用复杂的算法。