我试图将不同大小的圆圈包装到一个矩形容器中，而不是包装在d3.js捆绑在一起的圆形容器中，在d3.layout.pack.
这是我想要实现的布局：
我找到了这篇关于这个问题的论文，但我不是一个数学家，无法彻底理解这篇文章并将它们转换为代码......</p>
任何人都可以建议我应该从哪里开始将其转换为 d3.js 布局插件，或者如果您已经可视化了类似于此布局的气泡，请建议您解决该问题的任何方向。
谢谢你。
问问题
17806 次
5 回答
30
这是您算法的实现。
我对其进行了相当多的调整，但我认为它的作用基本相同。
包围圈
我使用了一个技巧来使计算更规律。
我没有使用定义边界框的线段，而是使用具有“无限”半径的圆，这可以被认为是线条的良好近似：
图片显示了当半径减小时 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 参数可以稍微改进一下，以便在值相等的情况下进行更美观的选择。
可能的演变
使用“无限半径”技巧，可以定义任意边界多边形。
如果您提供一个函数来检查一个圆是否适合所述多边形，那么该算法没有理由不产生结果。
这个结果是否有效是另一个问题:)。
于 2014-02-06T20:05:16.600 回答
24
完全不同的方法...
正如我在评论中提到的，可以将d3 集群力布局调整为一种启发式方法，通过逐渐改变比例直到你有一个紧密的配合来将圆圈安装到盒子中。
到目前为止的结果并不完美，所以我提出了几个版本：
选项 1，在调整圆重叠之前将框压缩到圆所占据的空间。结果非常紧凑，但是在盒子的墙壁和彼此之间夹住的圆圈之间有轻微的重叠，如果没有冲突就无法移动：
https ://jsfiddle.net/LeGfW/2/
选项 2，在分离重叠的圆圈后挤入框内。这避免了重叠，但包装并不是最佳的，因为我们不会将圆圈相互推入以迫使它们展开以填充矩形的长尺寸：
https ://jsfiddle.net/LeGfW/3/
选项 3，快乐的媒体，在调整重叠后再次挤压，但挤压因子是基于房间宽度和高度尺寸的平均值，而不是最小房间，所以它会一直挤压直到宽度和高度都被填满：
https://jsfiddle.net/LeGfW/5/
关键代码由updateBubblesforce tick 调用的方法和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;})
}
于 2014-02-07T02:12:59.983 回答
5
好吧，这远非最佳包装，但其他人可以尝试击败它。
更新了，但还是不太好
关键代码，比如：
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;
});
}
}
于 2014-02-02T04:29:17.793 回答
1
如果您主要关心的是在矩形内找到紧密排列的不同大小的圆圈，那么不幸的是，您将不得不实现新的 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');
于 2012-11-21T20:02:19.347 回答
-1
有一种更好的方法可以做到这一点——使用 Mitchell 的最佳拟合算法。
这是一般模式：
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;
};
}
});
}
参见例如随机数据。
于 2016-06-08T21:57:05.607 回答