日历事件的可视化.布局具有最大宽度的事件的算法

Question

我需要你的算法帮助(它将在客户端用javascript开发,但并不重要,我对算法本身最感兴趣)布置日历事件,以便每个事件框都有最大宽度.请看下面的图片:

Y轴是时间.因此,如果"测试事件"在中午开始(例如)并且没有更多与它相交,则需要整个100%的宽度."每周评论"与"Tumbling YMCA"和"Anna/Amelia"相交,但后两者不相交,所以他们都填满了50%.Test3,Test4和Test5都是相交的,因此每个的最大宽度为33.3%.但Test7为66%,因为Test3的修复率为33%(见上文),因此需要占用所有可用空间,即66%.

我需要一个算法如何解决这个问题.

提前致谢

Answer 1

1. 想象一下只有左边缘的无限网格.
2. 每个事件都是一个单元格宽度,高度和垂直位置根据开始和结束时间固定.
3. 尝试将每个事件放在尽可能远的列中,而不与该列中任何早期事件相交.
4. 然后,当放置每个连接的事件组时,它们的实际宽度将是该组使用的最大列数的1/n.
5. 您还可以在最左侧和右侧展开事件以消耗任何剩余空间.

/// 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:如果有足够的空间,现在将事件向右扩展.

Answer 2

接受的答案描述了一个包含5个步骤的算法.在接受的答案的注释中链接的示例实现仅实现步骤1到4.步骤5是确保最右边的事件使用所有可用空间.参见OP提供的图像中的事件7.

我通过添加所述算法的第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:这应该是对已接受答案的评论.不幸的是,我没有评论的权限.

Answer 3

这是使用 Typescript 为 React 实现的相同算法。你必须调整它来满足你的需求（当然），但它应该对任何使用 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).
function collides(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.
function expand(
  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)))
      return true;
    colSpan += 1;
    return false;
  });
  return colSpan;
}

// Each group contains columns of events that overlap.
const groups: Meeting[][][] = [];
// Each column contains events that do not overlap.
let columns: Meeting[][] = [];
let lastEventEnding: 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) return 1;
    if (e1.to < e2.to) return -1;
    if (e1.to > e2.to) return 1;
    return 0;
  })
  .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 (
  <div
    key={nanoid()}
    className={styles.cell}
    ref={cellRef}
  >
    {today && (
      <div style={{ top }} className={styles.indicator}>
        <div className={styles.dot} />
        <div className={styles.line} />
      </div>
    )}
    {groups.map((cols: Meeting[][]) =>
      cols.map((col: Meeting[], colIdx) =>
        col.map((e: Meeting) => (
          <MeetingItem
            now={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>
);

您可以在此处查看完整的源代码。我承认这是一个非常固执己见的实现，但它会对我有所帮助。