алгоритм распространения предметов вокруг круга около их стартовых позиций

Question

Я работаю над диаграммой, в которой есть множество предметов вокруг круга. Для каждого элемента у меня есть радиан, который позволяет мне помещать его в правильное положение, но у меня есть перекрытия, и я хотел бы распространять предметы, но чтобы они оставались рядом (как можно ближе) к их исходным позициям.

Во избежание совпадений каждый элемент должен быть не менее 7 градусов от любого смежного элемента. Всегда будет достаточно места для всех предметов по всему кругу - максимум 20 предметов, для каждого предмета может быть 18 степеней разделения (не то, чтобы это когда-либо происходило именно так), но вполне вероятно, что я буду имеют до 6 или 8 элементов, сгруппированных в области и, возможно, нескольких кластеров.

Чаще всего у меня будет от 10 до 12 предметов, но чтобы было легко проиллюстрировать - скажем, у меня есть 5 предметов на расстоянии 1 градуса: [1,2,3,4,5]. В идеале результат будет [349,356,3,10,17] - каждый элемент 7 градусов от любого другого предмета с пунктом 3 остается неизменным, но все предметы остаются как можно ближе к их исходным позициям.

Конечно, когда у меня есть все 20 предметов - я рискую переместить предмет в другой предмет. Возьмем аналогичный пример: [340,1,2,3,4,5]. То же, что и выше, кроме перемещения с 1 по 346, приведет к другому перекрытию.

Полный список предметов радианов, знает ли кто-нибудь о методе выполнения того, что я пытаюсь сделать?

Я просто не могу понять, как это осуществить.

Answer 1

У меня была проблема с другим подходом.

Идея состоит в том, чтобы добавлять объекты в круг по одному.
Каждый объект определяет вокруг него зону столкновения.

Когда новый объект добавлен, он проверяется на предмет столкновения с существующими.
Если возникает столкновение, новые объекты добавляются в «группу столкновений», содержащую все объекты, для которых требуются относительные корректировки положения, чтобы избежать совпадения друг с другом.
Если не обнаружено совпадений, создается новая группа столкновений, содержащая только новый объект.

После принятия нового объекта группа будет охватывать часть круга, центрированную вокруг его объектов, центра тяжести и достаточно широкую, чтобы удерживать все объекты без перекрытия.

Каждый раз, когда группа столкновений растет, она проверяется против всех других групп для перекрытия и объединяется с первой обнаруженной группой пересечения.
Процесс повторяется с полученной группой до тех пор, пока не будет выполнено больше сливаний.

После того, как все объекты были добавлены, в каждой группе вычисляются корректировки положения для равномерного распределения объектов.

---

См скрипку 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 переходы обработки действительно несложный), но мне кажется, выполнять работу в большинстве случаев. Я бы сказал, что это достаточно хорошо для доказательства концепции.

Этот алгоритм не обеспечивает соблюдение вашего требования о максимальном (угловом) расстоянии между исходным и скорректированным позициями. С другой стороны, он не гарантирует совпадения, если имеется достаточно места для размещения всех объектов в окружности.

Answer 2

Создайте массив из {item, itemAngle, itemDisplayAngle} из ваших предметов.
Имейте пункт ItemDisplayAngle, установленный в itemAngle изначально.
Сортировка массива itemAngle.
Затем проведите по массиву, и если расстояние между двумя последовательными элементами меньше 7, сдвиньте элементы 7 вправо, если помещение не будет выполнено. Следите, расстояние должно быть% 360, и вы должны следить за первыми элементами массива, если угол + 7> 360.
Повторите шаг выше, пока не была выполнена никакая операция.

Редактировать: иметь минимальный спрэд, решение довольно похоже, немного сложнее объяснить: если спред составляет < 7, то вам нужно переместить каждый элемент на (7 - текущий спред)/2
Но, конечно, вы должны проверить, можете ли вы, как слева, так и справа от вас, перемещать предметы. Я думаю, что если вы не можете использовать полураспространение, вы должны проверить, можете ли вы переместить правый элемент вправо или левый элемент влево. Таким образом, у вас оптимальное размещение.