空间填充不等大小的圆圈

Question

这是我的问题:

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

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

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

我的第一个"蛮力"想法如下:

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

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

编辑

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

Answer 1

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

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

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

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

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

以下是此实现的一些结果(它花了我大约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; row<gridRows; row++)
      {
        float distanceFromTop = y;
        float distanceFromBottom = height-y;
        for (int col=0; col<gridColumns; col++)
        {
          int i = row*gridColumns+col;
          dist[i]=(distanceFromTop<distanceFromBottom?distanceFromTop:distanceFromBottom);
        }
        y+=gridSize;
      }
      float x = gridSize/2.0;
      for (int col=0; col<gridColumns; col++)
      {
        float distanceFromLeft = x;
        float distanceFromRight = width-x;
        for (int row=0; row<gridRows; row++)
        {
          int i = row*gridColumns+col;
          if (dist[i]>distanceFromLeft) dist[i] = distanceFromLeft;
          if (dist[i]>distanceFromRight) dist[i] = distanceFromRight;
        }
        x+=gridSize;
      }
    }

    void drawCircles()
    {
      for (int circle = 0; circle<getNrOfCircles(); circle++)
      {
        // We assume circles are sorted large to small!
        float radius = getRadiusOfCircle( circle ); 

        // Find gridpoint with largest distance from anything
        int i=0;
        int maxR = 0;
        int maxC = 0;
        float maxDist = dist[0];

        for (int r=0; r<gridRows; r++) 
          for (int c=0; c<gridColumns; c++)
          {
            if (maxDist<dist[i]) {
              maxR= r; maxC= c; maxDist = dist[i];
            }
            i++;
          }

        // Calculate position of grid point
        float x = gridSize/2.0 + maxC*gridSize;
        float y = gridSize/2.0 + maxR*gridSize;

        // Apply some random Jitter
        float offset = (maxDist-radius)/2.0;
        x += (rand()/(float)RAND_MAX - 0.5) * 2 * offset;
        y += (rand()/(float)RAND_MAX - 0.5) * 2 * offset;


        drawCircle(x,y,radius);


        // Update Distance array with new circle;
        i=0;
        float yy = gridSize/2.0;
        for (int r=0; r<gridRows; r++)
        {
          float xx = gridSize/2.0;
          for (int c=0; c<gridColumns; c++)
          {
            float d2 = (xx-x)*(xx-x)+(yy-y)*(yy-y);

            // Naive implementation
            // float d = sqrt(d2) - radius;
            // if (dist[i]>d) 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;
        }
      }
    }