这是算法的实现。

我对它进行了相当多的调整，但我认为它的作用基本相同。

边界圆

我使用了一个技巧来使计算更加规律。

我没有使用定义边界框的线段，而是使用具有“无限”半径的圆，这可以被认为是线的一个很好的近似：

图片显示了当半径减小时 4 个边界圆的样子。它们被计算为穿过边界框的角并在半径增加时向实际边收敛。

“角”圆（如算法所称）都被计算为一对圆的切线，从而消除了特殊的圆+线段或线段+线段的情况。

这也大大简化了启动条件。
该算法只是从四个边界圆开始，一次添加一个圆，使用贪婪的启发式 lambda 参数来选择“最佳”位置。

最佳匹配策略

原始算法不会生成最小的矩形来容纳所有圆
（它只是尝试将一堆圆放入给定的矩形中）。

我在它上面添加了一个简单的二分搜索来猜测最小表面（这会产生给定纵横比的最小边界矩形）。

代码

这是一个小提琴

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

表现

代码没有优化，有利于可读性（或者我希望:)）。

计算时间急剧上升。
您可以安全地放置大约 20 个圆圈，但任何超过 100 的圆圈都会使您的浏览器爬行。

出于某种原因，它在 FireFox 上比在 IE11 上快得多。

包装效率

该算法在相同大小的圆上效果很差（它找不到正方形中 20 个圆的著名蜂窝图案），但在广泛的随机半径分布上效果很好。

美学

对于相同大小的圆圈，结果非常难看。
没有尝试将圆圈聚集在一起，因此如果算法认为两种可能性是等效的，则只是随机选择一种。

我怀疑可以稍微改进 lambda 参数，以便在值相等的情况下做出更美观的选择。

可能的演变

使用“无限半径”技巧，可以定义任意边界多边形。

如果您提供一个函数来检查圆是否适合所述多边形，则算法没有理由不产生结果。

这个结果是否有效是另一个问题:)。

一种完全不同的方法......

正如我在评论中提到的，d3 集群力布局可以改编成一种启发式方法，用于将圆圈拟合到盒子中，通过逐渐改变比例直到你有一个紧密的配合。

到目前为止的结果并不完美，所以我提出了几个版本：

选项 1，在调整圆重叠之前，将框挤压到圆所占据的空间。结果非常紧凑，但在盒子壁之间夹住的圆圈之间有轻微的重叠，相互之间无法移动，没有冲突：https :
//jsfiddle.net/LeGfW/2/

选项2，将重叠的圆圈分开后挤进盒子里。这避免了重叠，但包装不是最佳的，因为我们从来没有将圆圈推入彼此以迫使它们展开以填充矩形的长尺寸：https :
//jsfiddle.net/LeGfW/3/

选项 3，happy medium，在调整重叠后再次挤压，但挤压因子是基于房间的宽度和高度尺寸的平均值，而不是最小房间，所以它会一直挤压，直到宽度和高度都被填满：
https://jsfiddle.net/LeGfW/5/

键码由的updateBubbles由力蜱调用的方法，并且collide被称为在第一行方法updateBubbles。这是“选项 3”版本：

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

嗯，这远非最佳包装，但其他人可以尝试击败它。

更新了，但仍然不是很好

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

关键代码，例如：

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

    }

}

如果您主要关心的是在矩形内找到紧密包装的不同大小的圆圈，那么不幸的是，您将不得不实施新的 d3 布局。我不知道已经编写的插件可以做到这一点。

但是，如果您要查找的是任何旧的矩形包装，那么您可以使用 d3 中提供的现有圆形包装算法d3.layout.pack。指定此布局的边界时，您指定的是矩形的尺寸。然后 d3 确定边界矩形将外接的圆，并使用该圆来可视化分层数据的根。因此，您可以做的是提供一个您实际上并未渲染的“虚拟”根节点，并将您想要可视化的真实数据作为该节点的子节点。

下面的代码示例，我也把它放在 bl.ocks.org 上，这样你就可以看到它的运行情况。

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');

有一个更好的方法来做到这一点——使用 Mitchell 的最佳拟合算法。

这是一般模式：

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

    });

  }

参见例如随机数据。