Visualisation des événements du calendrier. Algorithme pour organiser des événements avec une largeur maximale

Question

J'ai besoin de votre aide pour un algorithme (il sera développé sur le côté client avec javascript, mais n'a pas vraiment d'importance, je suis surtout intéressé par l'algorithme lui-même) à la pose des événements de calendrier, de sorte que chaque boîte a une largeur maximale. Veuillez voir l'image suivante:

L'axe Y est le temps. Donc, si "Test event" débute à midi (par exemple) et rien de plus coupe avec elle, il prend toute la largeur 100%. "Revue hebdomadaire" croise "Tumbling YMCA" et "Anna/Amelia", mais les deux derniers ne sont pas croisées, afin de remplir tous les 50%. Test3, Test4 et Test5 sont tous d'intersection, de sorte que la largeur maximale est de 33,3% pour chacun. Mais Test7 est de 66% depuis Test3 est de 33% à taux fixe (voir ci-dessus) , de sorte qu'il prend tout l'espace disponible , qui est de 66%.

J'ai besoin d'un algorithme à mettre en cela.

Merci d'avance

Answer 1

1. Pensez à un nombre illimité de grille avec juste un bord gauche.
2. Chaque événement est une cellule de largeur, et la hauteur et la position verticale est fixe basé sur le commencement et la fin.
3. Essayez de placer chaque événement dans une colonne de gauche aussi loin que possible, sans intersection avant les événements de cette colonne.
4. Ensuite, lors de chaque groupe d'événements est placé, leur largeur sera de 1/n de la le nombre maximal de colonnes utilisées par le groupe.
5. Vous pouvez également étendre les événements à l'extrême gauche et le droit d'utiliser tout l'espace restant.

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

Edit: Maintenant trie les événements, au lieu de supposer qu'ils sont triées.

Edit2: élargit les événements vers la droite, si il y a assez d'espace.

Answer 2

C'est presque parfait. Le problème est que toutes les colonnes du groupe ont la même largeur. Cela ne fonctionne pas pour le dernier groupe de l'image: "Test 7" occupe les 2/3 de la largeur. Mais avec cet algorithme, "Test 7" prend 1/3 de la largeur. Je n'arrive pas à comprendre comment améliorer cela encore plus pour éviter les trous vides.