这是您的算法的实现。
我对它做了很多调整,但我认为它基本上做了同样的事情。
边界圆
我使用了一个技巧来使计算更加规则。
我没有使用定义边界框的线段,而是使用具有“无限”半径的圆,这可以被认为是线的良好近似:
该图显示了半径减小时 4 个边界圆的样子。经过计算,它们会穿过边界框的角点,并在半径增大时向实际边收敛。
“角”圆(算法如此称呼它们)都被计算为一对圆的切线,从而消除了特殊的圆+线段或线段+线段情况。
这也大大简化了启动条件。
该算法简单地从四个边界圆开始,然后一次添加一个圆,使用贪婪启发式 lambda 参数来选择“最佳”位置。
最适合策略
原始算法不会产生容纳所有圆的最小矩形
(它只是尝试将一堆圆放入给定的矩形中)。
我在其顶部添加了一个简单的二分搜索来猜测最小表面(这会产生给定纵横比的最小边界矩形)。
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;
}
};
表现
该代码未进行优化,以提高可读性(或者我希望如此:))。
计算时间急剧增加。
您可以安全地放置大约 20 个圆圈,但任何超过 100 个圆圈都会使您的浏览器爬行。
由于某种原因,FireFox 上的速度比 IE11 上快得多。
包装效率
该算法在相同大小的圆上效果很差(它无法找到正方形中 20 个圆的著名蜂窝图案),但在广泛的随机半径分布上效果很好。
美学
对于相同大小的圆圈来说,结果是相当难看的。
没有尝试将圆圈聚集在一起,因此如果算法认为两种可能性相同,则只是随机选择一种。
我怀疑 lambda 参数可以稍微细化一下,以便在值相等的情况下提供更美观的选择。
可能的演变
通过“无限半径”技巧,可以定义任意边界多边形。
如果您提供一个函数来检查圆是否适合所述多边形,则该算法没有理由不产生结果。
这个结果是否有效是另一个问题:)。