将不同大小的圆圈打包成矩形 - d3.js [英] Packing different sized circles into rectangle - d3.js
问题描述
我试图将不同大小的圆装入一个矩形容器，而不是装入 d3.js 捆绑在 d3.layout 下的圆形容器中.pack.
这是我想要实现的布局:
我发现
var Packer = function (circles, ratio){this.circles = 圆圈；this.ratio = 比率 ||1;this.list = this.solve();}Packer.prototype = {//尝试将所有圆放入给定表面的矩形中计算:函数(表面){//检查圆形是否在我们的矩形内函数 in_rect(半径，中心){if (center.x - radius <- w/2) 返回 false;如果(center.x + radius > w/2)返回false；if (center.y - radius <- h/2) 返回 false;如果(center.y + radius > h/2)返回false；返回真；}//近似一个具有无限"半径圆的线段函数 bounding_circle (x0, y0, x1, y1){var xm = Math.abs ((x1-x0)*w);var ym = Math.abs ((y1-y0)*h);var m = xm >嗯?xm : ym;var theta = Math.asin(m/4/bounding_r);var r = bounding_r * Math.cos (theta);返回新圆(bounding_r，新点 (r*(y0-y1)/2+(x0+x1)*w/4,r*(x1-x0)/2+(y0+y1)*h/4))；}//返回两个圆的角位置功能角(半径，c1，c2){var u = c1.c.vect(c2.c);//c1 到 c2 向量var A = u.norm();if (A == 0) return []//相同的中心u = u.mult(1/A);//c1 到 c2 一元向量//计算 (u,v) 基中的 c1 和 c2 交点坐标var B = c1.r+半径；var C = c2.r+半径；如果 (A > (B + C)) 返回 [];//距离太远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 = 新点(base.x -u.y * y，base.y + u.x * y)；var p2 = 新点(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));返回资源；}///////////////////////////////////////////////////////////////////从表面推导出起始尺寸var bounding_r = Math.sqrt(surface) * 100;//无限"半径var w = this.w = Math.sqrt (surface * this.ratio);var h = this.h = this.w/this.ratio;//放置我们的边界圆变量放置=[bounding_circle ( 1, 1, 1, -1),bounding_circle ( 1, -1, -1, -1),bounding_circle (-1, -1, -1, 1),bounding_circle (-1, 1, 1, 1)];//初始化我们的矩形列表var unplaced = this.circles.slice(0);//克隆数组while (unplaced.length > 0){//计算未放置圆的所有可能位置var 拉姆达 = {};var 圈 = {};for (var i = 0 ; i != unplaced.length ; i++){var lambda_min = 1e10;lambda[i] = -1e10;//将当前圆与所有可能的放置圆对匹配for (var j = 0 ; j lambda_max){lambda_max = lambda[i];i_max = i;}}//如果没有圆适合则失败如果(i_max == -1)中断；//放置选定的圆unplaced.splice(i_max,1);放置.推(圈[i_max])；}//返回除四个边界圆之外的所有放置的圆this.tmp_bounds =placed.splice (0, 4);返回放置；},//找到适合所有圆的最小矩形解决:函数(){//计算圆的总表面无功表面= 0;for (var i = 0 ; i != this.circles.length ; i++){表面 += Math.PI * Math.pow(this.circles[i],2);}//设置合适的精度var 限制 = 表面/1000；var step = 表面/2；var res = [];而(步>限制){varplacement = this.compute.call(this,surface);console.log ("放置",placement.length,"out of",this.circles.length,"for surface",surface);if (placement.length != this.circles.length){表面 += 台阶；}别的{res = 位置；this.bounds = this.tmp_bounds;表面 -= 台阶；}步骤/= 2;}返回资源；}}; 性能
代码没有优化，有利于可读性(或者我希望:)).
计算时间急剧增加.
您可以安全地放置大约 20 个圆圈，但任何超过 100 的圆圈都会使您的浏览器爬行.
出于某种原因，它在 FireFox 上比在 IE11 上快得多.
包装效率
该算法在相同大小的圆上效果很差(它找不到正方形中 20 个圆的著名蜂窝图案)，但在广泛的随机半径分布上效果很好.
美学
对于相同大小的圆圈，结果非常难看.
没有尝试将圆圈聚集在一起，因此如果算法认为两种可能性是等价的，则只是随机选择一种.
我怀疑可以稍微改进 lambda 参数，以便在值相等的情况下做出更美观的选择.
可能的演变
使用无限半径"技巧，可以定义任意边界多边形.
如果您提供一个函数来检查一个圆是否适合所述多边形，则算法没有理由不产生结果.
这个结果是否有效是另一个问题:)
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.
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 :).
这篇关于将不同大小的圆圈打包成矩形 - d3.js的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
