Space filling with circles of unequal size

Question

Here is my problem:

• I have a bunch of circles that I need to display inside a canvas.
• There are an arbitrary number of circles, each with a predefined radius.
• The summed area of circles is always smaller than the area of the canvas.

I want to position the circles so that they take up the maximal space available inside the canvas, without touching each other. My goal is to achieve a visually pleasing effect where the circles appear well distributed inside the canvas. I don't know if this is really "space filling", as my goal is not to minimize the distance between elements, but rather to maximize it.

Here is an example of what I am trying to achieve:

My first "brute force" idea was the following:

1. For each circle: calculate the shortest distance between its border and each other circle's border; sum all of these distances, call that X.
2. Calculate the sum of all X's.
3. Randomly change the distances between the circles.
4. Redo 1-3 for a preset number of iterations and take the maximal value obtained at step (2).

However, this does not seem elegant; I'm sure there is a better way to do it. Is there any existing algorithm to achieve such a layout? Is there any existing library that I could use (JavaScript or Ruby) to achieve this?

Edit

Here is a Javascript version of the accepted answer, which uses Raphael to draw the circles.

Answer 1

I would try to insert sphere after sphere (largest first). Each one is added in the largest available space, with some random jitter.

One relatively easy way to find (more or less) the largest available space, is to imagine a grid of points on your view and store for each grid point (in a 2D array) the closest distance to any item: edge or sphere, whichever is closest. This array is updated as each new sphere is added.

To add a new sphere, just take the grid point with highest distance and apply some random jitter (you actually know how much you can jitter, because you know the distance to the closest item). (I would randomize not more than (d-r)/2 where d is the distance in the array and r is the radius of the sphere to add.

Updating this array after adding another circle is no rocket science: you calculate for each grid point the distance to newly added sphere and replace the stored value if that was larger.

It is possible that your grid is too coarse, and you can't add any more circle (when the 2D array contains no distances larger than the radius of the circle to add). Then you have to increase (e.g. double) the grid resolution before continuing.

Here are some result of this implementation (it took me about 100 lines of code)

• 100 Circles of varying size

• 500 Circles of varying size

• 100 Circles of same size

And here is some rough C++ code (just the algorithm, don't expect this to compile)

    // 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;
        }
      }
    }

Answer 2

Perhaps some application of force-directed layout would be useful.