Packing different sized circles into rectangle - d

Question

I was trying to pack circles of different sizes into a rectangular container, not packing in circular container that d3.js bundled with, under d3.layout.pack.

here's the layout I want to achieve:

I've found this paper on this matter, but I am not a math guy to understand the article throughly and convert them into code…

Anyone can suggest where I should start to convert this into d3.js layout plugin, or if you have visualized bubbles similar to this layout, please suggest any direction you took to solve that.

Thank you.

Answer 1

If your primary concern finding a tight packing of different-sized circles within a rectangle, then unfortunately you'll have to implement a new d3 layout. I don't know of a plugin that's already written that will do this.

However, if what you're looking for is any old packing into a rectangle, then you can use the the existing circle packing algorithm that d3 provides in d3.layout.pack. When you specify the bounds for this layout, you're specifying the dimensions of a rectangle. d3 then determines a circle that the bounding rectangle will circumscribe, and uses that circle to visualize the root of the hierarchical data. So what you can do is provide a "dummy" root node which you don't actually render, and have the real data that you want to visualize be the children of that node.

Code example below, and I also put it up on bl.ocks.org so you can see it in action.

var w = 640,
    h = 480;

var data = {
  name : "root",
  children : [
    { name: '1', size: 100 }, { name: '2', size: 85 },
    { name: '3', size: 70 } , { name: '4', size: 55 },
    { name: '5', size: 40 } , { name: '6', size: 25 },
    { name: '7', size: 10 } ,
  ]
}

var canvas = d3.select("#canvas")
  .append("svg:svg")
  .attr('width', w)
  .attr('height', h);

var nodes = d3.layout.pack()
  .value(function(d) { return d.size; })
  .size([w, h])
  .nodes(data);

// Get rid of root node
nodes.shift();

canvas.selectAll('circles')
    .data(nodes)
  .enter().append('svg:circle')
    .attr('cx', function(d) { return d.x; })
    .attr('cy', function(d) { return d.y; })
    .attr('r', function(d) { return d.r; })
    .attr('fill', 'white')
    .attr('stroke', 'grey');

Answer 2

There's a much better way to do this -- using Mitchell's Best Fit algorithm.

This is the general pattern:

function drawCircles() { 
  var w = (parseInt(d3.select(".circles-div").style('width'), 10)) * 0.34,
    h = 350;

  d3.csv('dataset.csv', function(error, data) {

    var maxRadius = 8, // maximum radius of circle
      padding = 3, // padding between circles; also minimum radius
      margin = {top: maxRadius, right: maxRadius, bottom: maxRadius, left: maxRadius},
      width = w - margin.left - margin.right,
      height = h - margin.top - margin.bottom;

     var color = d3.scale.linear()
      .domain([50,10])
      .range(['#666','#efefef'])
      .interpolate(d3.interpolateHcl);

    var logscale = d3.scale.linear()
        .range([0,8]);

    logscale.domain([0,500])

    var k = 1, // initial number of candidates to consider per circle
        m = 100, // initial number of circles to add per frame
        n = data.length, // remaining number of circles to add
        newCircle = bestCircleGenerator(maxRadius, padding);

    var svg = d3.select(".circles-div").append("svg")
        .attr("width", w)
        .attr("height", h)
      .append("g")
        .attr('class','bubbles')
        .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

    d3.timer(function() {
      for (var i = 0; i < m && --n >= 0; ++i) {

        var maxR = logscale(data[n]['Radius_value'])

        var circle = newCircle(k);

        svg.append("circle")
            .attr("cx", circle[0])
            .attr("cy", circle[1])
            .attr("r", 0)
            .style('fill', color(data[n]['Color_value']))
          .transition()
            .attr("r", logscale(data[n]['Radius_value']));

        if (k < 500) k *= 1.01, m *= .998;
      }
      return !n;
    });

    function bestCircleGenerator(maxRadius, padding) {

      var quadtree = d3.geom.quadtree().extent([[0, 0], [width, height]])([]),
      searchRadius = maxRadius * 2,
      maxRadius2 = maxRadius * maxRadius;

      return function(k) {

        var bestX, bestY, bestDistance = 0;

        for (var i = 0; i < k || bestDistance < padding; ++i) {
          var x = Math.random() * width,
              y = Math.random() * height,
              rx1 = x - searchRadius,
              rx2 = x + searchRadius,
              ry1 = y - searchRadius,
              ry2 = y + searchRadius,
              minDistance = maxRadius; // minimum distance for this candidate

          quadtree.visit(function(quad, x1, y1, x2, y2) {
            if (p = quad.point) {
              var p,
                  dx = x - p[0],
                  dy = y - p[1],
                  d2 = dx * dx + dy * dy,
                  r2 = p[2] * p[2];
              if (d2 < r2) return minDistance = 0, true; // within a circle
              var d = Math.sqrt(d2) - p[2];
              if (d < minDistance) minDistance = d;
            }
            return !minDistance || x1 > rx2 || x2 < rx1 || y1 > ry2 || y2 < ry1; // or outside search radius
          });

          if (minDistance > bestDistance) bestX = x, bestY = y, bestDistance = minDistance;
        }

        var best = [bestX, bestY, bestDistance - padding];
        quadtree.add(best);
        return best;
      };
    }

    });

  }

See for example with random data.

Answer 3

A completely different approach...

As I mentioned in a comment, a d3 cluster-force layout could be adapted into a heuristic method for fitting the circles into the box, by progressively changing the scale until you have a tight fit.

Results so far are not perfect, so I present a few versions:

Option 1, squeezes in the box to the space occupied by the circles before adjusting for circle overlap. The result is very tightly packed, but with slight overlap between circles that get caught between the walls of the box and each other, unable to move without a conflict:
https://jsfiddle.net/LeGfW/2/

Option 2, squeezes in the box after separating overlapped circles. This avoids overlap, but the packing isn't optimum since we don't ever push the circles into each other to force them to spread out to fill the long dimension of the rectangle:
https://jsfiddle.net/LeGfW/3/

Option 3, the happy medium, again squeezes in after adjusting for overlap, but the squeeze factor is based on average out the room in width and height dimensions, instead of the minimum room, so it keeps squeezing until both width and height are filled:
https://jsfiddle.net/LeGfW/5/

Key code consists of the updateBubbles method called by the force tick, and the collide method which is called in the first line of updateBubbles. This is the "option 3" version:

// Create a function for this tick round,
// with a new quadtree to detect collisions 
// between a given data element and all
// others in the layout, or the walls of the box.

//keep track of max and min positions from the quadtree
var bubbleExtent;
function collide(alpha) {
  var quadtree = d3.geom.quadtree(data);
  var maxRadius = Math.sqrt(dataMax);
  var scaledPadding = padding/scaleFactor;
  var boxWidth = width/scaleFactor;
  var boxHeight = height/scaleFactor;

    //re-set max/min values to min=+infinity, max=-infinity:
  bubbleExtent = [[Infinity, Infinity],[-Infinity, -Infinity]];

  return function(d) {

      //check if it is pushing out of box:
    var r = Math.sqrt(d.size) + scaledPadding,
        nx1 = d.x - r,
        nx2 = d.x + r,
        ny1 = d.y - r,
        ny2 = d.y + r;

      if (nx1 < 0) {
           d.x = r;
      }
      if (nx2 > boxWidth) {
           d.x = boxWidth - r;
      }
      if (ny1 < 0) {
           d.y = r;
      }
      if (ny2 > boxHeight) {
           d.y = boxHeight - r;
      }


    //check for collisions
    r = r + maxRadius, 
        //radius to center of any possible conflicting nodes
        nx1 = d.x - r,
        nx2 = d.x + r,
        ny1 = d.y - r,
        ny2 = d.y + r;

    quadtree.visit(function(quad, x1, y1, x2, y2) {
      if (quad.point && (quad.point !== d)) {
        var x = d.x - quad.point.x,
            y = d.y - quad.point.y,
            l = Math.sqrt(x * x + y * y),
            r = Math.sqrt(d.size) + Math.sqrt(quad.point.size)
                    + scaledPadding;
        if (l < r) {
          l = (l - r) / l * alpha;
          d.x -= x *= l;
          d.y -= y *= l;
          quad.point.x += x;
          quad.point.y += y;
        }
      }
      return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
    });

    //update max and min
    r = r-maxRadius; //return to radius for just this node
    bubbleExtent[0][0] = Math.min(bubbleExtent[0][0], 
                                  d.x - r);
    bubbleExtent[0][1] = Math.min(bubbleExtent[0][1], 
                                  d.y - r);
    bubbleExtent[1][0] = Math.max(bubbleExtent[1][0], 
                                  d.x + r);
    bubbleExtent[1][1] = Math.max(bubbleExtent[1][1], 
                                  d.y + r);

  };
}  

function updateBubbles() {

    bubbles
        .each( collide(0.5) ); //check for collisions   

    //update the scale to squeeze in the box 
    //to match the current extent of the bubbles
    var bubbleWidth = bubbleExtent[1][0] - bubbleExtent[0][0];
    var bubbleHeight = bubbleExtent[1][1] - bubbleExtent[0][1];

    scaleFactor = (height/bubbleHeight +
                           width/bubbleWidth)/2; //average
    /*
    console.log("Box dimensions:", [height, width]);
    console.log("Bubble dimensions:", [bubbleHeight, bubbleWidth]);
    console.log("ScaledBubble:", [scaleFactor*bubbleHeight,
                                 scaleFactor*bubbleWidth]);
    //*/

    rScale
        .range([0,  Math.sqrt(dataMax)*scaleFactor]);

    //shift the bubble cluster to the top left of the box
    bubbles
        .each( function(d){
            d.x -= bubbleExtent[0][0];
            d.y -= bubbleExtent[0][1];
        });

    //update positions and size according to current scale:
    bubbles
        .attr("r", function(d){return rScale(d.size);} )
        .attr("cx", function(d){return scaleFactor*d.x;})
        .attr("cy", function(d){return scaleFactor*d.y;})
}

Answer 4

Here is a go at the implementation of your algorithm.

I tweaked it quite a bit, but I think it does basically the same thing.

Bounding circles

I used a trick to make the computation more regular.

Instead of segments defining the bounding box, I used circles with "infinite" radii, that can be considered a good approximation of lines:

The picture shows what the 4 bounding circles look like when the radius is decreased. They are computed to pass through the corners of the bounding box and converge toward the actual sides when the radius grows.

The "corner" circles (as the algorithm calls them) are all computed as tangents to a pair of circles, thus eliminating the special circle+segment or segment+segment cases.

This also simplifies the start condition greatly.
The algorithm simply starts with the four bounding circles and adds one circle at a time, using the greedy heuristic lambda parameter to pick the "best" location.

Best fit strategy

The original algorithm does not produce the smallest rectangle to hold all the circles
(it simply tries to fit a bunch of circles into a given rectangle).

I have added a simple dichotomic search on top of it to guess the minimal surface (which yields the smallest bounding rectangle for a given aspect ratio).

The code

Here is a fiddle

var Packer = function (circles, ratio)
{
    this.circles = circles;
    this.ratio   = ratio || 1;
    this.list = this.solve();
}

Packer.prototype = {
    // try to fit all circles into a rectangle of a given surface
    compute: function (surface)
    {
        // check if a circle is inside our rectangle
        function in_rect (radius, center)
        {
            if (center.x - radius < - w/2) return false;
            if (center.x + radius >   w/2) return false;
            if (center.y - radius < - h/2) return false;
            if (center.y + radius >   h/2) return false;
            return true;
        }

        // approximate a segment with an "infinite" radius circle
        function bounding_circle (x0, y0, x1, y1)
        {
            var xm = Math.abs ((x1-x0)*w);
            var ym = Math.abs ((y1-y0)*h);
            var m = xm > ym ? xm : ym;
            var theta = Math.asin(m/4/bounding_r);
            var r = bounding_r * Math.cos (theta);
            return new Circle (bounding_r, 
                new Point (r*(y0-y1)/2+(x0+x1)*w/4, 
                           r*(x1-x0)/2+(y0+y1)*h/4));
        }

        // return the corner placements for two circles
        function corner (radius, c1, c2)
        {
            var u = c1.c.vect(c2.c); // c1 to c2 vector
            var A = u.norm();
            if (A == 0) return [] // same centers
            u = u.mult(1/A); // c1 to c2 unary vector
            // compute c1 and c2 intersection coordinates in (u,v) base
            var B = c1.r+radius;
            var C = c2.r+radius;
            if (A > (B + C)) return []; // too far apart
            var x = (A + (B*B-C*C)/A)/2;
            var y = Math.sqrt (B*B - x*x);
            var base = c1.c.add (u.mult(x));

            var res = [];
            var p1 = new Point (base.x -u.y * y, base.y + u.x * y);
            var p2 = new Point (base.x +u.y * y, base.y - u.x * y);
            if (in_rect(radius, p1)) res.push(new Circle (radius, p1));
            if (in_rect(radius, p2)) res.push(new Circle (radius, p2));
            return res;
        }

        /////////////////////////////////////////////////////////////////

        // deduce starting dimensions from surface
        var bounding_r = Math.sqrt(surface) * 100; // "infinite" radius
        var w = this.w = Math.sqrt (surface * this.ratio);
        var h = this.h = this.w/this.ratio;

        // place our bounding circles
        var placed=[
            bounding_circle ( 1,  1,  1, -1),
            bounding_circle ( 1, -1, -1, -1),
            bounding_circle (-1, -1, -1,  1),
            bounding_circle (-1,  1,  1,  1)];

        // Initialize our rectangles list
        var unplaced = this.circles.slice(0); // clones the array
        while (unplaced.length > 0)
        {
            // compute all possible placements of the unplaced circles
            var lambda = {};
            var circle = {};
            for (var i = 0 ; i != unplaced.length ; i++)
            {
                var lambda_min = 1e10;
                lambda[i] = -1e10;
                // match current circle against all possible pairs of placed circles
                for (var j = 0   ; j < placed.length ; j++)
                for (var k = j+1 ; k < placed.length ; k++)
                {
                    // find corner placement
                    var corners = corner (unplaced[i], placed[j], placed[k]);

                    // check each placement
                    for (var c = 0 ; c != corners.length ; c++)
                    {
                        // check for overlap and compute min distance
                        var d_min = 1e10;
                        for (var l = 0 ; l != placed.length ; l++)
                        {
                            // skip the two circles used for the placement
                            if (l==j || l==k) continue;

                            // compute distance from current circle
                            var d = placed[l].distance (corners[c]);
                            if (d < 0) break; // circles overlap

                            if (d < d_min) d_min = d;
                        }
                        if (l == placed.length) // no overlap
                        {
                            if (d_min < lambda_min)
                            {
                                lambda_min = d_min;
                                lambda[i] = 1- d_min/unplaced[i];
                                circle[i] = corners[c];
                            }
                        }
                    }
                }
            }

            // select the circle with maximal gain
            var lambda_max = -1e10;
            var i_max = -1;
            for (var i = 0 ; i != unplaced.length ; i++)
            {
                if (lambda[i] > lambda_max)
                {
                    lambda_max = lambda[i];
                    i_max = i;
                }
            }

            // failure if no circle fits
            if (i_max == -1) break;

            // place the selected circle
            unplaced.splice(i_max,1);
            placed.push (circle[i_max]);
        }

        // return all placed circles except the four bounding circles
        this.tmp_bounds = placed.splice (0, 4);
        return placed;
    },

    // find the smallest rectangle to fit all circles
    solve: function ()
    {
        // compute total surface of the circles
        var surface = 0;
        for (var i = 0 ; i != this.circles.length ; i++)
        {
            surface += Math.PI * Math.pow(this.circles[i],2);
        }

        // set a suitable precision
        var limit = surface/1000;

        var step = surface/2;
        var res = [];
        while (step > limit)
        {
            var placement = this.compute.call (this, surface);
console.log ("placed",placement.length,"out of",this.circles.length,"for surface", surface);
            if (placement.length != this.circles.length)
            {
                surface += step;
            }
            else
            {
                res = placement;
                this.bounds = this.tmp_bounds;
                surface -= step;
            }
            step /= 2;
        }
        return res; 
    }
};

Performance

The code is not optimized, to favor readability (or so I hope :)).

The computation time rises pretty steeply.
You can safely place about 20 circles, but anything above 100 will make your browser crawl.

For some reason, it is way faster on FireFox than on IE11.

Packing efficiency

The algorithm works quite poorly on identically-sized circles (it cannot find the famous honeycomb pattern for 20 circles in a square), but pretty well on a wide distribution of random radii.

Aesthetics

The result is pretty ungainly for identical-sized circles.
There is no attempt to bunch the circles together, so if two possibilities are deemed equivalent by the algorithm, one is just picked at random.

I suspect the lambda parameter could be refined a bit to allow for a more aesthetic choice in case of equal values.

Possible evolutions

With the "infinite radii" trick, it becomes possible to define an arbitrary bounding polygon.

If you provide a function to check if a circle fits into the said polygon, there is no reason the algorithm should not produce a result.

Whether this result would be efficient is another question :).

Answer 5

Well, this is far from optimal packing, but it's something that others can try to beat.

Updated, but still not great

https://jsfiddle.net/LF9Yp/6/

Key code, such as it is:

var points = [[]]; //positioned circles, by row
function assignNextPosition(d,index) {
    console.log("fitting circle ", index, d.size);
    var i, j, n;
    var radiusPlus = rScale(d.size) + padding;
    if (!points[0].length) { //this is first object
       d.x = d.y = radiusPlus; 
       points[0].push(d);
       points[0].width = points[0].height = 2*radiusPlus;
       points[0].base = 0;
       return;
    }
    i = 0; n = points.length - 1; 
    var tooTight, lastRow, left, rp2, hyp;
    while ((tooTight = (width - points[i].width < 2*radiusPlus)
            ||( points[i+1]? 
                points[i+1].base - points[i].base < 2*radiusPlus 
                : false) ) 
          &&(i < n) ) i++;
           //skim through rows to see if any can fit this circle

    if (!tooTight) { console.log("fit on row ", i);
        //one of the rows had room
        lastRow = points[i];
        j=lastRow.length;

        if (i == 0) {
          //top row, position tight to last circle and wall
            d.y = radiusPlus;
            rp2 = (rScale(lastRow[j-1].size) + padding);
            d.x = lastRow[j-1].x + Math.sqrt(
                Math.pow( (radiusPlus + rp2), 2)
                - Math.pow( (radiusPlus - rp2),2) );
        }
        else {
           //position tight to three closest circles/wall
           //(left, top left and top right)
            //or (left, top left and right wall)
           var left = lastRow[j-1];
           d.x = left.x + rScale(left.size) + padding + radiusPlus;
           var prevRow = points[i - 1];       
           j = prevRow.length;
           while ((j--) && (prevRow[j].x > d.x));
           j = Math.max(j,0);
           if (j + 1 < prevRow.length) {
               console.log("fit between", prevRow[j], prevRow[j+1]);
               d.y = prevRow[j].y 
               + (Math.sqrt(Math.pow((radiusPlus + 
                           rScale(prevRow[j].size) +padding), 2) 
                           - Math.pow( (d.x - prevRow[j].x),2)
                       )||0);
              j++;
              d.y = Math.max(d.y, prevRow[j].y 
               + (Math.sqrt(Math.pow((radiusPlus + 
                           rScale(prevRow[j].size) +padding), 2) 
                           - Math.pow( (d.x - prevRow[j].x),2)
                       )||0)  );
           }
           else { //tuck tight against wall
               console.log("fit between", prevRow[j], "wall");
            d.x = width - radiusPlus;
            rp2 = (rScale(prevRow[j].size) + padding);
            d.y = prevRow[j].y + (Math.sqrt(
                Math.pow( (radiusPlus + rp2), 2)
                - Math.pow( (d.x - prevRow[j].x),2) )||0);
            if (i > 1)
                d.y = Math.max(d.y, points[i-2].height + radiusPlus);
           }
        }

        lastRow.push(d); 
        lastRow.width = d.x + radiusPlus;
        lastRow.height = Math.max(lastRow.height, 
                                  d.y + radiusPlus);
        lastRow.base = Math.min(lastRow.base,
                                d.y - radiusPlus);

    } else { console.log("new row ", points.length)
        prevRow = points[points.length -1];
        j=prevRow.length;
        while(j--) {
            var testY = prevRow[j].y + rScale(prevRow[j].size) + padding
                  + radiusPlus;
            if (testY + radiusPlus < prevRow.height) {
                //tuck row in gap
                d.x = prevRow[j].x;
                d.y = testY;
            }
        }
        if (!d.x) {//start row at left
          d.x = radiusPlus;
          d.y = prevRow.height + radiusPlus;
        }
        var newRow = [d];
        newRow.width = d.x + radiusPlus;
        newRow.height = Math.max(d.y + radiusPlus, prevRow.height);
        newRow.base = d.y - radiusPlus;
        points.push(newRow); 
    } 
            if (!d.y) console.log("error",d);
    if (d.y + radiusPlus > height) {
      //change rScale by the ratio this exceeds the height
      var scaleFactor = height/(d.y + radiusPlus);
      rScale.range([0, rScale.range()[1]*scaleFactor]);

      //recalculate all positions
      points.forEach(function(row, j){
            row.forEach(function(d, i) {
               d.x = (d.x - i*2*padding)*scaleFactor + i*2*padding;
               d.y = (d.y - i*2*padding)*scaleFactor + i*2*padding;
            });
            row.width *= scaleFactor;
      });

    }

}