javascript - 将不同大小的圆圈打包成矩形 - d3.js

Question

我试图将不同大小的圆圈打包到一个矩形容器中，而不是打包到 d3.js 捆绑的圆形容器中，在 d3.layout 下.pack.

这是我想要实现的布局:

我找到了 this paper在这件事上，但我不是数学家，无法透彻理解这篇文章并将其转换为代码......

任何人都可以建议我应该从哪里开始将其转换为 d3.js 布局插件，或者如果您有与此布局类似的可视化气泡，请提出解决该问题的任何方向。

谢谢。

Answer 1

下面是算法的实现。

我对它做了很多调整，但我认为它的作用基本相同。

边界圈

我使用了一个小技巧来使计算更加规律。

我没有使用线段来定义边界框，而是使用了具有“无限”半径的圆，这可以被认为是线的一个很好的近似值:

图片显示了当半径减小时 4 个边界圆的样子。它们被计算为穿过边界框的 Angular ，并在半径增加时向实际边收敛。

“Angular ”圆(如算法所称)都被计算为一对圆的切线，从而消除了特殊的圆+线段或线段+线段的情况。

这也大大简化了启动条件。​​
该算法简单地从四个边界圆开始，一次添加一个圆，使用贪婪的启发式 lambda 参数来选择“最佳”位置。

最佳匹配策略

原算法并没有产生能容纳所有圆的最小矩形
(它只是试图将一堆圆圈放入给定的矩形中)。

我在它上面添加了一个简单的二分法搜索来猜测最小表面(对于给定的纵横比，它产生最小的边界矩形)。

代码

这里是 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 参数可以稍微改进一下，以便在值相等的情况下提供更美观的选择。

可能的演变

使用“无限半径”技巧，可以定义任意边界多边形。

如果您提供了一个函数来检查圆是否适合所述多边形，则算法没有理由不产生结果。

这个结果是否有效是另一个问题:)。