包装不同大小的圆形变成长方形 - d3.js [英] Packing different sized circles into rectangle - d3.js
问题描述
我是想收拾的不同大小的圆形变成方形容器，在没有包装的圆形容器 d3.js 捆绑在一起， d3.layout.pack 。
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:
我发现<一href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.5620&rep=rep1&type=pdf">this纸在这个问题上，但我不是一个数学的家伙理解文章透了，并把它们转换成code ...
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…
任何人都可以建议我应该在哪里开始转换到这一点d3.js布局插件，或者如果您已经显现泡沫类似这样的布局，请建议你把要解决的任何方向。
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.
感谢你。
推荐答案
下面是一个去你的算法的实现。
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.
我用一招，使计算更加规则。
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:
图为什么4包围的圈子看起来像当半径减小。它们被计算穿过边界框的拐角和汇聚于实际两侧当半径增大。
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.
这也大大简化了启动条件。
该算法只是开始的四个边界的圈子，并增加了一圈的时候，采用启发式贪婪的lambda参数挑选最好的位置。
This also simplifies the start condition greatly.
The algorithm simply starts with the four bounding circles and adds one circle at the time, using the greedy heuristic lambda parameter to pick the "best" location.
原算法不会产生容纳所有圈的最小矩形
（它只是尝试，以适应一堆圈成一个给定的矩形）。
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).
下面是小提琴
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;
}
};
性能
在code未优化，有利于可读性（或者我希望如此：））
Performance
The code is not optimized, to favor readability (or so I hope :)).
中的计算时间急剧上升pretty的。照片 您可以放心地把约20圈，但任何高于100将让你的浏览器抓取。
The computation time rises pretty steeply.
You can safely place about 20 circles, but anything above 100 will make your browser crawl.
由于某些原因，这是远远快于火狐比IE11。
For some reason, it is way faster on FireFox than on IE11.
该算法相当不好的相同大小的圆圈（实在找不到20圈在广场上著名的蜂巢图案），但pretty的以及在广泛随机半径的分布。
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.
结果是pretty的笨拙了相同大小的圆。
有没有尝试一堆圈在一起，因此，如果两种可能性都是由算法视为等同，人们只是随机挑选。
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.
通过无限半径招，就可以定义一个任意的边界多边形。
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 :).
这篇关于包装不同大小的圆形变成长方形 - d3.js的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
