javascript - 将项目围绕其起始位置附近的圆展开的算法

Question

我正在制作一个图表，该图表在一个圆圈周围有许多项目。对于每个项目，我都有一个弧度，可以让我将它放在正确的位置 - 但我有重叠，我想将项目展开，但让它们保持在(尽可能靠近)原始位置附近。

为避免重叠，每件商品必须与任何相邻商品至少成 7 度 Angular 。圆圈周围的所有项目总会有足够的空间 - 最多 20 个项目，每个项目有可能有 18 度的分离(并不是说它会以这种方式发生)，但我很可能会最多有 6 或 8 个项目聚集在一个区域中，并且可能有多个集群。

大多数情况下，我会有 10 到 12 个项目，但为了便于说明 - 假设我有 5 个项目，相隔 1 度:[1,2,3,4,5]。理想情况下，结果将是 [349,356,3,10,17] - 每个项目与任何其他项目 7 度 Angular ，项目 3 保持不变，但所有项目都尽可能靠近其原始位置。

当然，当我拥有所有 20 个项目时 - 我冒着将一个项目移到另一个项目的风险。举一个类似的例子:[340,1,2,3,4,5]。与上面相同 - 除了将 1 移动到 346 会导致另一个重叠。

给出项目弧度的完整列表，有没有人知道完成我正在尝试做的事情的方法？

我似乎无法弄清楚如何完成它。

Answer 1

我用不同的方法解决了你的问题。

这个想法是一次一个地向圆圈中添加对象。
每个对象都在其周围定义了一个碰撞区域。

添加新对象时，会检查它是否与现有对象发生碰撞。
如果发生碰撞，新对象将添加到“碰撞组”，其中包含需要相对位置调整以避免彼此重叠的所有对象。
如果未检测到重叠，则会创建一个仅包含新对象的新碰撞组。

接受一个新对象后，一个组将覆盖以其对象重心为中心的圆圈的一部分，其宽度刚好足以容纳所有对象而不重叠。

每次碰撞组增长时，都会检查所有其他组是否重叠，并与检测到的第一个相交组合并。
对生成的组重复该过程，直到无法进行更多合并。

添加所有对象后，将在每个组内计算位置调整以均匀分布对象。

---

参见 fiddle here

var CollisionResolver = function (radius)
{
    this.radius = radius || 3.5; // degrees
    this.groups = [];
    this.collision = {};
    this.objects = {};
    this.num_obj = 0;
}

CollisionResolver.prototype = 
{
    // add an object to the circle
    add: function (obj)
    {
        function sort_group ()
        {
            group.elem.sort(function(a,b) {return a.pos>b.pos; });
            var middle = 0;
            for (var i = 0; i != group.elem.length ; i++) middle += group.elem[i].pos;
            middle /=  group.elem.length;
            var range = this.radius * group.elem.length;
            group.min = middle-range;
            group.max = middle+range;

            // see if the expanded group now overlaps another
            for (var g = 0 ; g != this.groups.length ; g++)
            {
                var group2 = this.groups[g];
                if (group2 == group) continue;
                for (var offset = 0 ; offset <720 ; offset += 360)
                {
                    if (  (group2.max+offset > group.min)
                       && (group2.min+offset < group.max))
                    {
                        // merge groups
                        for (var i = 0 ; i != group2.elem.length ; i++)
                            group2.elem[i].pos += offset;
                        group.elem = group.elem.concat(group2.elem);
                        this.groups.splice (g, 1);

                        // try again with the merged group
                        sort_group.call (this,group);
                        return;
                    }
                }
            }
        }

        // store the object
        obj.id = this.num_obj;
        this.objects[this.num_obj++] = obj;

        // see if the object falls within a collision group
        for (var g in this.groups)
        {
            var group = this.groups[g];
            for (var offset = 0 ; offset <720 ; offset += 360)
            {
                if (  (obj.pos+offset+this.radius > group.min)
                   && (obj.pos+offset-this.radius < group.max))
                {
                    // insert the object into the collision group
                    obj.pos += offset;
                    group.elem.push (obj);
                    sort_group.call (this, group);
                    return;
                }
            }
        }

        // create a new singleton collision group
        var group = { 
            elem: [obj],
            min :obj.pos-this.radius,
            max :obj.pos+this.radius };
        this.groups.push (group);
    },

    resolve: function ()
    {
        // spread the objects inside each group
        var groups = this.groups;
        for (var i = 0 ; i != groups.length ; i++)
        {
            var group = groups[i];
            for (var o = 0 ; o != group.elem.length ; o++)
            {
                group.elem[o].pos = (group.min + (2*o+1) * this.radius + 360) % 360;
            }
        }

        // return the positions
        var res = [];
        for (var i = 0 ; i != this.num_obj ; i++) res.push (this.objects[i].pos);
        return res;
    }
}

function spread (positions, radius)
{
    var collider = new CollisionResolver (radius);

    // initialize object positions
    for (var i = 0; i != positions.length ; i++)
    {
        collider.add ({ pos:positions[i]} );
    }

    // resolve collisions
    return collider.resolve();  
}

它的边缘仍然有点粗糙(我不太确定 360°->0 过渡处理是否真的万无一失)，但它似乎在大多数情况下都能胜任。我想说这足以证明概念。

此算法不会强制要求原始位置和调整后位置之间的最大( Angular )距离。另一方面，只要有足够的空间将所有对象放入圆圈，它就保证不会重叠。