Визуализация событий календаря. Алгоритм для компоновки событий с максимальной шириной

Ответ 1

• Подумайте о неограниченной сетке с левым краем.
• Каждое событие имеет ширину в одну ячейку, а высота и вертикальное положение фиксируются в зависимости от времени начала и окончания.
• Попытайтесь разместить каждое событие в столбце как можно дальше, без пересечения какого-либо более раннего события в этом столбце.
• Затем, когда размещается каждая связанная группа событий, их фактическая ширина будет равна 1/n от максимального количества столбцов, используемых группой.
• Вы также можете расширить события в левом и правом местах, чтобы использовать оставшееся пространство.

/// Pick the left and right positions of each event, such that there are no overlap.
/// Step 3 in the algorithm.
void LayoutEvents(IEnumerable<Event> events)
{
    var columns = new List<List<Event>>();
    DateTime? lastEventEnding = null;
    foreach (var ev in events.OrderBy(ev => ev.Start).ThenBy(ev => ev.End))
    {
        if (ev.Start >= lastEventEnding)
        {
            PackEvents(columns);
            columns.Clear();
            lastEventEnding = null;
        }
        bool placed = false;
        foreach (var col in columns)
        {
            if (!col.Last().CollidesWith(ev))
            {
                col.Add(ev);
                placed = true;
                break;
            }
        }
        if (!placed)
        {
            columns.Add(new List<Event> { ev });
        }
        if (lastEventEnding == null || ev.End > lastEventEnding.Value)
        {
            lastEventEnding = ev.End;
        }
    }
    if (columns.Count > 0)
    {
        PackEvents(columns);
    }
}

/// Set the left and right positions for each event in the connected group.
/// Step 4 in the algorithm.
void PackEvents(List<List<Event>> columns)
{
    float numColumns = columns.Count;
    int iColumn = 0;
    foreach (var col in columns)
    {
        foreach (var ev in col)
        {
            int colSpan = ExpandEvent(ev, iColumn, columns);
            ev.Left = iColumn / numColumns;
            ev.Right = (iColumn + colSpan) / numColumns;
        }
        iColumn++;
    }
}

/// Checks how many columns the event can expand into, without colliding with
/// other events.
/// Step 5 in the algorithm.
int ExpandEvent(Event ev, int iColumn, List<List<Event>> columns)
{
    int colSpan = 1;
    foreach (var col in columns.Skip(iColumn + 1))
    {
        foreach (var ev1 in col)
        {
            if (ev1.CollidesWith(ev))
            {
                return colSpan;
            }
        }
        colSpan++;
    }
    return colSpan;
}

Изменить: Теперь сортирует события, а не предполагает, что они отсортированы.

Edit2: Теперь расширяется событие вправо, если достаточно места.

Ответ 2

Принятый ответ описывает алгоритм с 5 шагами. Пример реализации, связанный в комментариях принятого ответа, реализует только шаги с 1 по 4. Шаг 5 состоит в том, чтобы убедиться, что самое правое событие использует все свободное пространство. См. Событие 7 в изображении, предоставленном OP.

Я расширил данную реализацию, добавив шаг 5 описанного алгоритма:

$( document ).ready( function( ) {
  var column_index = 0;
  $( '#timesheet-events .daysheet-container' ).each( function() {

    var block_width = $(this).width();
    var columns = [];
    var lastEventEnding = null;

    // Create an array of all events
    var events = $('.bubble_selector', this).map(function(index, o) {
      o = $(o);
      var top = o.offset().top;
      return {
        'obj': o,
        'top': top,
        'bottom': top + o.height()
      };
    }).get();

    // Sort it by starting time, and then by ending time.
    events = events.sort(function(e1,e2) {
      if (e1.top < e2.top) return -1;
      if (e1.top > e2.top) return 1;
      if (e1.bottom < e2.bottom) return -1;
      if (e1.bottom > e2.bottom) return 1;
      return 0;
    });

    // Iterate over the sorted array
    $(events).each(function(index, e) {

      // Check if a new event group needs to be started
      if (lastEventEnding !== null && e.top >= lastEventEnding) {
        // The latest event is later than any of the event in the 
        // current group. There is no overlap. Output the current 
        // event group and start a new event group.
        PackEvents( columns, block_width );
        columns = [];  // This starts new event group.
        lastEventEnding = null;
      }

      // Try to place the event inside the existing columns
      var placed = false;
      for (var i = 0; i < columns.length; i++) {                   
        var col = columns[ i ];
        if (!collidesWith( col[col.length-1], e ) ) {
          col.push(e);
          placed = true;
          break;
        }
      }

      // It was not possible to place the event. Add a new column 
      // for the current event group.
      if (!placed) {
        columns.push([e]);
      }

      // Remember the latest event end time of the current group. 
      // This is later used to determine if a new groups starts.
      if (lastEventEnding === null || e.bottom > lastEventEnding) {
        lastEventEnding = e.bottom;
      }
    });

    if (columns.length > 0) {
      PackEvents( columns, block_width );
    }
  });
});


// Function does the layout for a group of events.
function PackEvents( columns, block_width )
{
  var n = columns.length;
  for (var i = 0; i < n; i++) {
    var col = columns[ i ];
    for (var j = 0; j < col.length; j++)
    {
      var bubble = col[j];
      var colSpan = ExpandEvent(bubble, i, columns);
      bubble.obj.css( 'left', (i / n)*100 + '%' );
      bubble.obj.css( 'width', block_width * colSpan / n - 1 );
    }
  }
}

// Check if two events collide.
function collidesWith( a, b )
{
  return a.bottom > b.top && a.top < b.bottom;
}

// Expand events at the far right to use up any remaining space. 
// Checks how many columns the event can expand into, without 
// colliding with other events. Step 5 in the algorithm.
function ExpandEvent(ev, iColumn, columns)
{
    var colSpan = 1;

    // To see the output without event expansion, uncomment 
    // the line below. Watch column 3 in the output.
    //return colSpan;

    for (var i = iColumn + 1; i < columns.length; i++) 
    {
      var col = columns[i];
      for (var j = 0; j < col.length; j++)
      {
        var ev1 = col[j];
        if (collidesWith(ev, ev1))
        {
           return colSpan;
        }
      }
      colSpan++;
    }
    return colSpan;
}

Рабочая демонстрация доступна на http://jsbin.com/detefuveta/edit?html,js,output См. Столбец 3 вывода для примеров расширения самых правых событий.

PS: Это должен быть комментарий к принятому ответу. К сожалению, у меня нет привилегий для комментариев.