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

Question

我试图将不同尺寸的圆圈装入一个矩形容器中,而不是装在下面d3.js捆绑的圆形容器中d3.layout.pack.

这是我想要实现的布局:

我已经在这个问题上找到了这篇论文,但我不是一个全面理解这篇文章并将它们转换成代码的数学家......

任何人都可以建议我应该在哪里开始将其转换为d3.js布局插件,或者如果你有类似于这种布局的可视化气泡,请建议你采取任何方向来解决这个问题.

谢谢.

Answer 1

以下是您的算法实现.

我调整了很多,但我认为它基本上是一样的.

边界圈

我用了一个技巧使计算更加规则.

我使用了具有"无限"半径的圆圈,而不是定义边界框的线段,这可以被认为是线条的良好近似:

图片显示了半径减小时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参数可以稍微改进一下,以便在值相等的情况下进行更美观的选择.

可能的演变

使用"无限半径"技巧,可以定义任意边界多边形.

如果您提供一个函数来检查圆是否适合所述多边形,则算法不应该产生结果.

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

Answer 2

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

正如我在评论中提到的那样,d3群集力布局可以通过逐步改变比例直到你有一个紧密的拟合来适应一种启发式方法,将圆圈拟合到框中.

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

选项1,在调整圆重叠之前,在框中挤压圆占据的空间.结果非常紧凑,但是在盒子的墙壁和彼此之间夹住的圆圈之间略有重叠,无法在没有冲突的情况下移动:https:
//jsfiddle.net/LeGfW/2/

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

选项3,快乐的介质,在调整重叠后再次挤压,但挤压系数是基于平均宽度和高度尺寸的房间,而不是最小的空间,所以它一直挤压,直到宽度和高度都填满:
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;})
}

Answer 3

嗯,这远非最佳包装,但它是其他人可以试图击败的东西.

更新了,但仍然不是很好

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

    }

}

Answer 4

如果您主要关心的是在矩形内找到紧密排列的不同大小的圆圈，那么不幸的是您必须实现新的 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');