Visualización de eventos de calendario. Algoritmo para maquetar eventos con ancho máximo

Question

Necesito tu ayuda con un algoritmo (se desarrollará en el lado del cliente con javascript, pero en realidad no importa, estoy interesado principalmente en el algoritmo mismo) presentando eventos de calendario para que cada caja de evento tiene ancho máximo. Por favor, vea la siguiente imagen:

eje Y es el tiempo. Entonces, si "Test event" comienza al mediodía (por ejemplo) y nada más se cruza con él, toma todo el ancho del 100%. La "revisión semanal" se cruza con "Tumbling YMCA" y "Anna/Amelia", pero las últimas dos no se cruzan, por lo que todas ocupan el 50%. Test3, Test4 y Test5 se están cruzando, por lo que el ancho máximo es 33.3% para cada uno. Pero Test7 es 66% ya que Test3 está fijado al 33% (ver arriba), por lo que toma todo el espacio disponible, que es 66%.

Necesito un algoritmo de cómo establecer esto.

Gracias de antemano

Answer 1

1. pensar en una red ilimitada con sólo un borde izquierdo.
2. Cada evento tiene una celda de ancho, y la altura y la posición vertical se fija en función de las horas de inicio y fin.
3. Intenta colocar cada evento en una columna lo más a la izquierda posible, sin que se corte ningún evento anterior en esa columna.
4. Luego, cuando se coloca cada grupo de eventos conectado, sus anchos reales serán 1/n del número máximo de columnas utilizadas por el grupo.
5. También podría expandir los eventos de extremo a extremo para agotar el espacio restante.

/// 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; 
} 

Editar: ahora ordena los acontecimientos, en lugar de asumir que está ordenada.

Edit2: Ahora expande los eventos a la derecha, si hay espacio suficiente.

Answer 2

La respuesta aceptada describe un algoritmo con 5 pasos. La implementación de ejemplo vinculada en los comentarios de la respuesta aceptada implementa solo los pasos 1 a 4. El paso 5 consiste en asegurarse de que el evento de la derecha use todo el espacio disponible. Ver el evento 7 en la imagen proporcionada por el OP.

I amplió la implementación dada mediante la adición de paso 5 del algoritmo descrito:

$(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; 
} 

Una demostración de trabajo está disponible en http://jsbin.com/detefuveta/edit?html,js,output véase la columna 3 de la salida para ejemplos de la ampliación de los eventos más a la derecha.

PD: Esto realmente debería ser un comentario a la respuesta aceptada. Lamentablemente, no tengo los privilegios para comentar.