将不同大小的圆形包装到矩形中 - d3.js [英] Packing different sized circles into rectangle - d3.js
问题描述
我在尝试将不同尺寸的圆形包装到矩形容器中，而不是包装在与 d3.js 捆绑的圆形容器中 d3.layout.pack 。
这里是我想实现的布局：
我找到
var Packer = function（circles，ratio）
{
this.circles = circles;
this.ratio = ratio || 1;
this.list = this.solve（）;
}
Packer.prototype = {
//尝试将所有圆拟合到给定曲面的矩形中
compute：function（surface）
{
//检查一个圆是否在我们的矩形内
function in_rect（radius，center）
{
if（center.x - radius< - w / 2）return假;
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;
}
//近似一个带有无限半径圆的段
function 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）;
return new Circle（bounding_r，
new Point（r *（y0-y1）/ 2 +（x0 + x1）* w / 4，
r *（x1-x0）/ 2 + （y0 + y1）* h / 4））;
}
//返回两个圆的拐角位置
函数角（radius，c1，c2）
{
var u = c1.c .vect（c2.c）; // c1 to c2 vector
var A = u.norm（）;
if（A == 0）return [] //相同中心
u = u.mult（1 / A）; // c1到c2一元向量
//计算c1和c2（u，v）中的交点坐标base
var B = c1.r + radius;
var C = c2.r + radius;
if（A>（B + C））return []; //太远了
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;
}
/////////////////////////////////////// ////////////////////////////
//从表面推导起始尺寸
var bounding_r = Math.sqrt（surface）* 100; //infiniteradius
var w = this.w = Math.sqrt（surface * this.ratio）;
var h = this.h = this.w / this.ratio;
//放置我们的边界圈
var puts = [
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 lambda = {};
var circle = {};
for（var i = 0; i！= unplaced.length; i ++）
{
var lambda_min = 1e10;
lambda [i] = -1e10;
//匹配当前圆与所有可能的放置圆对
for（var j = 0; j
{
//找到角位置
var corners = corner（unplaced [i]，placement [j]，placed [k]
//检查每个位置
for（var c = 0; c！= corners.length; c ++）
{
//检查重叠和计算min distance
var d_min = 1e10;
for（var l = 0; l！= placed.length; l ++）
{
//跳过用于放置的两个圆
if（l == j | | l == k）continue;
//计算当前圆圈的距离
var d = placement [l] .distance（corners [c]）;
if（d <0）break; //圆圈重叠
if（d
if（l == placed.length）//无重叠
{
if（d_min
lambda_min = d_min ;
lambda [i] = 1- d_min / unplaced [i];
circle [i] = corners [c];
}
}
}
}
}
//选择具有最大增益的圆
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;
}
}
//如果没有圆则失败
if（i_max == -1）break;
//放置选定的圆
unplaced.splice（i_max，1）;
placing.push（circle [i_max]）;
}
//返回除了四个边界圆圈之外的所有放置的圆圈
this.tmp_bounds = placed.splice（0，4）;
return put;
}，
//找到适合所有圆的最小矩形
求解：function（）
{
//计算圆的总表面
var surface = 0;
for（var i = 0; i！= this.circles.length; i ++）
{
surface + = Math.PI * Math.pow（this.circles [i]，2 ）;
}
//设置合适的精度
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个圆圈，
由于某种原因，FireFox比IE11更快。
包装效率
该算法在相同大小的圆圈上工作相当糟糕（在正方形中找不到20个圆圈的着名蜂窝图案）
美学
对于相同大小的圆圈，结果是相当不明显的。
没有尝试将这些圈子组合在一起，因此如果算法认为两个可能性相同，则只是随机选择一个。
可能的演变
$ b我想知道lambda参数可以细化一些，以便在相同值的情况下有更美观的选择。 $ b
使用无限半径技巧，可以定义任意的边界多边形。
如果您提供一个函数来检查圆是否适合所述多边形，没有理由该算法不应该产生结果。
这个结果是否有效是另一个问题：）
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 the 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屋！
