問題描述

我需要你的算法幫助(它將在客戶端使用 javascript 開發(fā)，但沒關(guān)系，我最感興趣的是算法本身)布置日歷事件，以便每個事件框都有最大寬度.請看下圖:

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 calendar events so that each event box has maximum width. Please see the following picture:

Y 軸是時間.因此，如果測試事件"在中午開始(例如)并且沒有更多的相交，它會占用整個 100% 的寬度.《每周回顧》與《翻滾的基督教青年會》和《安娜/阿米莉亞》有交集，但后兩者沒有交集，所以都占滿了 50%.Test3、Test4 和 Test5 都相交，因此每個的最大寬度為 33.3%.但是 Test7 是 66%，因為 Test3 是 33% 固定的(見上文)，所以它占用了所有可用空間，即 66%.

Y axis is time. So if "Test event" starts at noon (for example) and nothing more intersects with it, it takes the whole 100% width. "Weekly review" intersects with "Tumbling YMCA" and "Anna/Amelia", but the latter two are not intersecting, so they all fill up 50%. Test3, Test4 and Test5 are all intersecting, so max width is 33.3% for each. But Test7 is 66% since Test3 is 33% fixed (see above) , so it takes all available space , which is 66%.

我需要一個算法來解決這個問題.

I need an algorithm how to lay this out.

提前致謝

推薦答案

1. 想象一個只有左邊緣的無限網(wǎng)格.
2. 每個事件都是一個單元格寬，高度和垂直位置根據(jù)開始和結(jié)束時間固定.
3. 嘗試將每個事件放在盡可能靠左的列中，不要與該列中任何較早的事件相交.
4. 然后，當放置每個連接的事件組時，它們的實際寬度將是該組使用的最大列數(shù)的 1/n.
5. 您還可以展開最左側(cè)和最右側(cè)的事件以使用剩余空間.

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

現(xiàn)在對事件進行排序，而不是假設(shè)它們已排序.

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

Edit2:如果有足夠的空間，現(xiàn)在向右展開事件.

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

這篇關(guān)于日歷事件的可視化.以最大寬度布局事件的算法的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！