javascript 将不同大小的圆圈打包成矩形 - d3.js

Packing different sized circles into rectangle - d3.js

提问by Hiroaki Yamane

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

我试图将不同大小的圆圈打包到一个矩形容器中，而不是打包在d3.js与d3.layout.pack.

here's the layout I want to achieve:

这是我想要实现的布局：

I've found this paperon 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.

任何人都可以建议我应该从哪里开始将其转换为 d3.js 布局插件，或者如果您已经看到与此布局类似的气泡，请建议您解决该问题的任何方向。

Thank you.

谢谢你。

回答by kuroi neko

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.

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

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.

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

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.

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

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

出于某种原因，它在 FireFox 上比在 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.

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

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.

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

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 :).

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

回答by AmeliaBR

A completely different approach...

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

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

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

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 beforeadjusting 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/

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

Option 2, squeezes in the box afterseparating 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/

选项2，将重叠的圆圈分开后挤进盒子里。这避免了重叠，但包装不是最佳的，因为我们从来没有将圆圈推入彼此以迫使它们展开以填充矩形的长尺寸：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/

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

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

键码由的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;})
}

回答by AmeliaBR

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/

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

    }

}

回答by seliopou

If your primary concern finding a tightpacking 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.

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

However, if what you're looking for is anyold 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.

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

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

下面的代码示例，我也把它放在 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');

回答by Learning stats by example

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

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

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 forexample with random data.

参见例如随机数据。