Visualization Of Calendar Events. Algorithm To Layout Events With Maximum Width

I need your help with an algorithm (it will be developed on client side with javascript, but doesn't really matter, I'm mostly interested in the algorithm itself) laying out calend

Solution 1:

1. Think of an unlimited grid with just a left edge.
2. Each event is one cell wide, and the height and vertical position is fixed based on starting and ending times.
3. Try to place each event in a column as far left as possible, without it intersecting any earlier event in that column.
4. Then, when each connected group of events is placed, their actual widths will be 1/n of the maximum number of columns used by the group.
5. You could also expand the events at the far left and right to use up any remaining space.

/// Pick the left and right positions of each event, such that there are no overlap./// Step 3 in the algorithm.voidLayoutEvents(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.voidPackEvents(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.intExpandEvent(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;
}

Edit: Now sorts the events, instead of assuming they is sorted.

Edit2: Now expands the events to the right, if there are enough space.

Solution 2:

The accepted answer describes an algorithm with 5 steps. The example implementation linked in the comments of the accepted answer implements only steps 1 to 4. Step 5 is about making sure the rightmost event uses all the space available. See event 7 in the image provided by the OP.

I expanded the given implementation by adding step 5 of the described algorithm:

$( 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 eventsvar 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) return1;
      if (e1.bottom < e2.bottom) return -1;
      if (e1.bottom > e2.bottom) return1;
      return0;
    });

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

      // Check if a new event group needs to be startedif (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 columnsvar 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.functionPackEvents( 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.functioncollidesWith( 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.functionExpandEvent(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;
}

A working demo is available at http://jsbin.com/detefuveta/edit?html,js,output See column 3 of the output for examples of expanding the rightmost events.

PS: This should really be a comment to the accepted answer. Unfortunately I don't have the privileges to comment.

Solution 3:

Here's the same algorithm implemented for React using Typescript. You'll have to tweak it to fit your needs (of course), but it should prove useful for anyone working in React:

// Place concurrent meetings side-by-side (like GCal).// @see {@link https://share.clickup.com/t/h/hpxh7u/WQO1OW4DQN0SIZD}// @see {@link https://stackoverflow.com/a/11323909/10023158}// @see {@link https://jsbin.com/detefuveta/edit}// Check if two events collide (i.e. overlap).functioncollides(a: Timeslot, b: Timeslot): boolean {
  return a.to > b.from && a.from < b.to;
}

// Expands events at the far right to use up any remaining// space. Returns the number of columns the event can// expand into, without colliding with other events.functionexpand(
  e: Meeting,
  colIdx: number,
  cols: Meeting[][]
): number {
  let colSpan = 1;
  cols.slice(colIdx + 1).some((col) => {
    if (col.some((evt) =>collides(e.time, evt.time)))
      returntrue;
    colSpan += 1;
    returnfalse;
  });
  return colSpan;
}

// Each group contains columns of events that overlap.constgroups: Meeting[][][] = [];
// Each column contains events that do not overlap.letcolumns: Meeting[][] = [];
letlastEventEnding: Date | undefined;
// Place each event into a column within an event group.
meetings
  .filter((m) => m.time.from.getDay() === day)
  .sort(({ time: e1 }, { time: e2 }) => {
    if (e1.from < e2.from) return -1;
    if (e1.from > e2.from) return1;
    if (e1.to < e2.to) return -1;
    if (e1.to > e2.to) return1;
    return0;
  })
  .forEach((e) => {
    // Check if a new event group needs to be started.if (
      lastEventEnding &&
      e.time.from >= lastEventEnding
    ) {
      // The event is later than any of the events in the// current group. There is no overlap. Output the// current event group and start a new one.
      groups.push(columns);
      columns = [];
      lastEventEnding = undefined;
    }

    // Try to place the event inside an existing column.let placed = false;
    columns.some((col) => {
      if (!collides(col[col.length - 1].time, e.time)) {
        col.push(e);
        placed = true;
      }
      return placed;
    });

    // It was not possible to place the event (it overlaps// with events in each existing column). Add a new column// to the current event group with the event in it.if (!placed) columns.push([e]);

    // Remember the last event end time of the current group.if (!lastEventEnding || e.time.to > lastEventEnding)
      lastEventEnding = e.time.to;
  });
groups.push(columns);

// Show current time indicator if today is current date.const date = getDateWithDay(day, startingDate);
const today =
  now.getFullYear() === date.getFullYear() &&
  now.getMonth() === date.getMonth() &&
  now.getDate() === date.getDate();
const { y: top } = getPosition(now);

return (
  <divkey={nanoid()}className={styles.cell}ref={cellRef}
  >
    {today && (
      <divstyle={{top }} className={styles.indicator}><divclassName={styles.dot} /><divclassName={styles.line} /></div>
    )}
    {groups.map((cols: Meeting[][]) =>
      cols.map((col: Meeting[], colIdx) =>
        col.map((e: Meeting) => (
          <MeetingItemnow={now}meeting={e}viewing={viewing}setViewing={setViewing}editing={editing}setEditing={setEditing}setEditRndVisible={setEditRndVisible}widthPercent={expand(e, colIdx, cols) / cols.length
            }
            leftPercent={colIdx / cols.length}
            key={e.id}
          />
        ))
      )
    )}
  </div>
);

You can see the full source-code here. I'll admit that this is a highly opinionated implementation, but it would've helped me so I'll post it here to see if it helps anyone else!