Twórz wykresy narracyjne w stylu xkcd

W jednym z bardziej kultowych pasków xkcd Randall Munroe przedstawił linie czasu kilku filmów na wykresach narracyjnych:

(Kliknij, aby zobaczyć większą wersję.)

Źródło: xkcd nr 657 .

Biorąc pod uwagę specyfikację osi czasu filmu (lub innej narracji), musisz wygenerować taki wykres. To konkurs popularności, więc wygra odpowiedź z największą liczbą głosów (netto).

Minimalne wymagania

Aby nieco zawęzić specyfikację, oto minimalny zestaw funkcji, które każda odpowiedź musi zaimplementować:

• Weź jako dane wejściowe listę nazw znaków, a następnie listę wydarzeń. Każde zdarzenie jest albo listą umierających znaków, albo listą grup znaków (oznaczających, które znaki są obecnie razem). Oto jeden przykład, w jaki sposób można zakodować narrację o Parku Jurajskim:

  ["T-Rex", "Raptor", "Raptor", "Raptor", "Malcolm", "Grant", "Sattler", "Gennaro",
   "Hammond", "Kids", "Muldoon", "Arnold", "Nedry", "Dilophosaurus"]
  [
    [[0],[1,2,3],[4],[5,6],[7,8,10,11,12],[9],[13]],
    [[0],[1,2,3],[4,7,5,6,8,9,10,11,12],[13]],
    [[0],[1,2,3],[4,7,5,6,8,9,10],[11,12],[13]],
    [[0],[1,2,3],[4,7,5,6,9],[8,10,11,12],[13]],
    [[0,4,7],[1,2,3],[5,9],[6,8,10,11],[12],[13]],
    [7],
    [[5,9],[0],[4,6,10],[1,2,3],[8,11],[12,13]],
    [12],
    [[0, 5, 9], [1, 2, 3], [4, 6, 10, 8, 11], [13]], 
    [[0], [5, 9], [1, 2], [3, 11], [4, 6, 10, 8], [13]], 
    [11], 
    [[0], [5, 9], [1, 2, 10], [3, 6], [4, 8], [13]], 
    [10], 
    [[0], [1, 2, 9], [5, 6], [3], [4, 8], [13]], 
    [[0], [1], [9, 5, 6], [3], [4, 8], [2], [13]], 
    [[0, 1, 9, 5, 6, 3], [4, 8], [2], [13]], 
    [1, 3], 
    [[0], [9, 5, 6, 3, 4, 8], [2], [13]]
  ]
  

  Np. Pierwsza linia oznacza, że ​​na początku mapy T-Rex jest samotny, trzy Raptory są razem, Malcolm jest sam, Grant i Sattler są razem, itp. Przedostatnie zdarzenie oznacza, że ​​dwa Raptory umierają .

  Jak dokładnie oczekujesz, że dane wejściowe zależą od Ciebie, o ile można określić tego rodzaju informacje. Np. Możesz użyć dowolnego wygodnego formatu listy. Możesz także oczekiwać, że postacie w wydarzeniach będą ponownie pełnymi nazwami postaci itp.

  Możesz (ale nie musisz) zakładać, że każda lista grup zawiera każdą żywą postać w dokładnie jednej grupie. Nie należy jednak zakładać, że grupy lub postacie w ramach jednego wydarzenia są w szczególnie dogodnej kolejności.

• Renderuj, aby wyświetlić ekran lub plik (jako grafikę wektorową lub rastrową) wykres, który ma jedną linię dla każdego znaku. Każda linia musi być oznaczona nazwą znaku na początku linii.

• Dla każdego normalnego zdarzenia musi istnieć jakiś przekrój wykresu, na którym grupy znaków są wyraźnie przypominane przez bliskość odpowiednich linii.
• Dla każdego zdarzenia śmierci wiersze odpowiednich znaków muszą kończyć się widocznym kroplem.
• Zdajesz nie trzeba powielać innych cech działek Randall, ani czy masz do odtworzenia jego styl rysowania. Proste linie z ostrymi zakrętami, wszystko w kolorze czarnym, bez dalszych etykiet i tytułu jest idealnie w porządku, aby wziąć udział w konkursie. Nie ma również potrzeby efektywnego wykorzystywania przestrzeni - np. Możesz potencjalnie uprościć algorytm, przesuwając tylko linie w dół, aby spotkać się z innymi postaciami, o ile istnieje zauważalny kierunek czasu.

Dodałem rozwiązanie referencyjne, które dokładnie spełnia te minimalne wymagania.

Czyni to ładnym

Jest to jednak konkurs popularności, dlatego możesz wdrożyć dowolną modę. Najważniejszym dodatkiem jest przyzwoity algorytm układania, który sprawia, że ​​wykres jest bardziej czytelny - np. Co sprawia, że ​​zakręty w liniach są łatwe do śledzenia i które zmniejszają liczbę koniecznych skrzyżowań linii. To jest podstawowy problem algorytmiczny tego wyzwania! Głosy decydują o skuteczności algorytmu w utrzymywaniu porządku w tabeli.

Ale oto kilka pomysłów, większość opartych na wykresach Randalla:

Dekoracje:

• Kolorowe linie.
• Tytuł fabuły.
• Kończy się linia etykietowania.
• Automatyczne ponowne znakowanie linii, które przeszły przez zajęty odcinek.
• Ręcznie rysowany styl (lub inny? Jak powiedziałem, nie ma potrzeby odtwarzania stylu Randall, jeśli masz lepszy pomysł) dla linii i czcionek.
• Konfigurowalna orientacja osi czasu.

Dodatkowa ekspresja:

• Nazwane wydarzenia / grupy / zgony.
• Znikające i ponownie pojawiające się linie.
• Postacie spóźniają się.
• Najważniejsze cechy, które wskazują (możliwe do przeniesienia?) Właściwości znaków (np. Patrz profil dzwonka na wykresie LotR).
• Kodowanie dodatkowych informacji w osi grupowania (np. Informacji geograficznych jak na wykresie LotR).
• Podróż w czasie?
• Alternatywne rzeczywistości?
• Postać zmieniająca się w inną?
• Dwie postacie się łączą? (Podział znaków?)
• 3D? (Jeśli naprawdę posuniesz się tak daleko, upewnij się, że faktycznie używasz dodatkowego wymiaru do wizualizacji czegoś!)
• Wszelkie inne istotne cechy, które mogą być przydatne do wizualizacji narracji filmu (lub książki itp.).

Oczywiście wiele z nich będzie wymagało dodatkowych danych wejściowych i możesz dowolnie rozszerzać swój format wejściowy, ale udokumentuj, w jaki sposób można wprowadzać dane.

Podaj jeden lub dwa przykłady, aby pochwalić się wdrożonymi funkcjami.

Twoje rozwiązanie powinno być w stanie poradzić sobie z każdym ważnym wkładem, ale jest absolutnie w porządku, jeśli lepiej pasuje do niektórych rodzajów narracji niż inne.

Kryteria głosowania

Nie mam złudzeń, że mógłbym powiedzieć ludziom, jak powinni wydawać głosy, ale oto kilka sugerowanych wskazówek w kolejności ich ważności:

• Potwierdź odpowiedzi, które wykorzystują luki, standardowe lub inne, lub zakoduj jeden lub więcej wyników.
• Nie oceniaj odpowiedzi, które nie spełniają minimalnych wymagań (bez względu na to, jak fantazyjna może być cała reszta).
• Przede wszystkim poprzyj dobre algorytmy układania. Obejmuje to odpowiedzi, które nie zajmują dużo miejsca w pionie, minimalizując przecinanie się linii, aby wykres był czytelny, lub które potrafią zakodować dodatkowe informacje w osi pionowej. Wizualizacja grup bez robienia wielkiego bałaganu powinna być głównym celem tego wyzwania, tak aby pozostał to programowy konkurs z interesującym problemem algorytmicznym w sercu.
• Upvote opcjonalne funkcje, które dodają ekspresyjnej mocy (tj. Nie są po prostu czystą dekoracją).
• Na koniec głosuj ładnie.

Python3 z numpy, scipy i matplotlib

edycja :

• Próbowałem utrzymać grupy w tej samej względnej pozycji między zdarzeniami, stąd sorted_eventfunkcja.
• Nowa funkcja do obliczania pozycji y znaków ( coords).
• Każde żywe wydarzenie jest teraz kreślone dwa razy, więc postacie lepiej trzymają się razem.
• Dodano legendę i usunięto etykietę osi.

import math
import numpy as np
from scipy.interpolate import interp1d
from matplotlib import cm, pyplot as plt


def sorted_event(prev, event):
    """ Returns a new sorted event, where the order of the groups is
    similar to the order in the previous event. """
    similarity = lambda a, b: len(set(a) & set(b)) - len(set(a) ^ set(b))
    most_similar = lambda g: max(prev, key=lambda pg: similarity(g, pg))
    return sorted(event, key=lambda g: prev.index(most_similar(g)))


def parse_data(chars, events):
    """ Turns the input data into 3 "tables":
    - characters: {character_id: character_name}
    - timelines: {character_id: [y0, y1, y2, ...],
    - deaths: {character_id: (x, y)}
    where x and y are the coordinates of a point in the xkcd like plot.
    """
    characters = dict(enumerate(chars))
    deaths = {}
    timelines = {char: [] for char in characters}

    def coords(character, event):
        for gi, group in enumerate(event):
            if character in group:
                ci = group.index(character)
                return (gi + 0.5 * ci / len(group)) / len(event)
        return None

    t = 0
    previous = events[0]
    for event in events:
        if isinstance(event[0], list):
            previous = event = sorted_event(previous, event)
            for character in [c for c in characters if c not in deaths]:
                timelines[character] += [coords(character, event)] * 2
            t += 2
        else:
            for char in set(event) - set(deaths):
                deaths[char] = (t-1, timelines[char][-1])

    return characters, timelines, deaths


def plot_data(chars, timelines, deaths):
    """ Draws a nice xkcd like movie timeline """

    plt.xkcd()  # because python :)

    fig = plt.figure(figsize=(16,8))
    ax = fig.add_subplot(111)
    ax.get_xaxis().set_visible(False)
    ax.get_yaxis().set_visible(False)
    ax.set_xlim([0, max(map(len, timelines.values()))])

    color_floats = np.linspace(0, 1, len(chars))
    color_of = lambda char_id: cm.Accent(color_floats[char_id])

    for char_id in sorted(chars):
        y = timelines[char_id]
        f = interp1d(np.linspace(0, len(y)-1, len(y)), y, kind=5)
        x = np.linspace(0, len(y)-1, len(y)*10)
        ax.plot(x, f(x), c=color_of(char_id))

    x, y = zip(*(deaths[char_id] for char_id in sorted(deaths)))
    ax.scatter(x, y, c=np.array(list(map(color_of, sorted(deaths)))), 
               zorder=99, s=40)

    ax.legend(list(map(chars.get, sorted(chars))), loc='best', ncol=4)
    fig.savefig('testplot.png')


if __name__ == '__main__':
    chars = [
        "T-Rex","Raptor","Raptor","Raptor","Malcolm","Grant","Sattler",
        "Gennaro","Hammond","Kids","Muldoon","Arnold","Nedry","Dilophosaurus"
    ]
    events = [
        [[0],[1,2,3],[4],[5,6],[7,8,10,11,12],[9],[13]],
        [[0],[1,2,3],[4,7,5,6,8,9,10,11,12],[13]],
        [[0],[1,2,3],[4,7,5,6,8,9,10],[11,12],[13]],
        [[0],[1,2,3],[4,7,5,6,9],[8,10,11,12],[13]],
        [[0,4,7],[1,2,3],[5,9],[6,8,10,11],[12],[13]],
        [7],
        [[5,9],[0],[4,6,10],[1,2,3],[8,11],[12,13]],
        [12],
        [[0,5,9],[1,2,3],[4,6,10,8,11],[13]],
        [[0],[5,9],[1,2],[3,11],[4,6,10,8],[13]],
        [11],
        [[0],[5,9],[1,2,10],[3,6],[4,8],[13]],
        [10],
        [[0],[1,2,9],[5,6],[3],[4,8],[13]],
        [[0],[1],[9,5,6],[3],[4,8],[2],[13]],
        [[0,1,9,5,6,3],[4,8],[2],[13]],
        [1,3],
        [[0],[9,5,6,3,4,8],[2],[13]]
    ]
    plot_data(*parse_data(chars, events))

T-SQL

Nie jestem zadowolony z tego jako wpisu, ale myślę, że to pytanie zasługuje przynajmniej na próbę. Spróbuję poprawić to później, jeśli pozwala, ale etykietowanie zawsze będzie problemem w SQL. Rozwiązanie wymaga SQL 2012+ i jest uruchamiane w SSMS (SQL Server Management Studio). Dane wyjściowe znajdują się na karcie wyników przestrzennych.

-- Variables for the input
DECLARE @actors NVARCHAR(MAX) = '["T-Rex", "Raptor", "Raptor", "Raptor", "Malcolm", "Grant", "Sattler", "Gennaro", "Hammond", "Kids", "Muldoon", "Arnold", "Nedry", "Dilophosaurus"]';
DECLARE @timeline NVARCHAR(MAX) = '
[
   [[1], [2, 3, 4], [5], [6, 7], [8, 9, 11, 12, 13], [10], [14]],
   [[1], [2, 3, 4], [5, 8, 6, 7, 9, 10, 11, 12, 13], [14]],
   [[1], [2, 3, 4], [5, 8, 6, 7, 9, 10, 11], [12, 13], [14]],
   [[1], [2, 3, 4], [5, 8, 6, 7, 10], [9, 11, 12, 13], [14]],
   [[1, 5, 8], [2, 3, 4], [6, 10], [7, 9, 11, 12], [13], [14]],
   [8],
   [[6, 10], [1], [5, 7, 11], [2, 3, 4], [9, 12], [13, 14]],
   [13],
   [[1, 6, 10], [2, 3, 4], [5, 7, 11, 9, 12], [14]],
   [[1], [6, 10], [2, 3], [4, 12], [5, 7, 11, 9], [14]],
   [12],
   [[1], [6, 10], [2, 3, 11], [4, 7], [5, 9], [14]],
   [11],
   [[1], [2, 3, 10], [6, 7], [4], [5, 9], [14]],
   [[1], [2], [10, 6, 7], [4], [5, 9], [3], [14]],
   [[1, 2, 10, 6, 7, 4], [5, 9], [3], [14]],
   [2, 4],
   [[1], [10, 6, 7, 5, 9], [3], [14]]
]
';

-- Populate Actor table
WITH actor(A) AS ( SELECT CAST(REPLACE(STUFF(REPLACE(REPLACE(@actors,', ',','),'","','</a><a>'),1,2,'<a>'),'"]','</a>') AS XML))
SELECT ROW_NUMBER() OVER (ORDER BY(SELECT \)) ActorID, a.n.value('.','varchar(50)') Name
INTO Actor
FROM actor CROSS APPLY A.nodes('/a') as a(n);

-- Populate Timeline Table
WITH Seq(L) AS (
    SELECT CAST(REPLACE(REPLACE(REPLACE(REPLACE(@timeline,'[','<e>'),']','</e>'),'</e>,<e>','</e><e>'),'</e>,','</e>') AS XML)
    ),
    TimeLine(N,Exerpt,Elem) AS (
    SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) N
        ,z.query('.')
        ,CAST(REPLACE(CAST(z.query('.') AS VARCHAR(MAX)),',','</e><e>') AS XML)
    FROM Seq 
        CROSS APPLY Seq.L.nodes('/e/e') AS Z(Z)
    ),
    Groups(N,G,Exerpt) AS (
    SELECT N, 
        ROW_NUMBER() OVER (PARTITION BY N ORDER BY CAST(SUBSTRING(node.value('.','varchar(50)'),1,ISNULL(NULLIF(CHARINDEX(',',node.value('.','varchar(50)')),0),99)-1) AS INT)), 
        CAST(REPLACE(CAST(node.query('.') AS VARCHAR(MAX)),',','</e><e>') AS XML) C
    FROM TimeLine 
        CROSS APPLY Exerpt.nodes('/e/e') as Z(node)
    WHERE Exerpt.exist('/e/e') = 1
    )
SELECT * 
INTO TimeLine
FROM (
    SELECT N, null G, null P, node.value('.','int') ActorID, 1 D 
    FROM TimeLine CROSS APPLY TimeLine.Elem.nodes('/e') AS E(node)
    WHERE Exerpt.exist('/e/e') = 0
    UNION ALL
    SELECT N, G, DENSE_RANK() OVER (PARTITION BY N, G ORDER BY node.value('.','int')), node.value('.','int') ActorID, 0
    FROM Groups CROSS APPLY Groups.Exerpt.nodes('/e') AS D(node)
    ) z;

-- Sort the entries again
WITH ReOrder AS (
            SELECT *, 
                ROW_NUMBER() OVER (PARTITION BY N,G ORDER BY PG, ActorID) PP, 
                COUNT(P) OVER (PARTITION BY N,G) CP, 
                MAX(G) OVER (PARTITION BY N) MG, 
                MAX(ActorID) OVER (ORDER BY (SELECT\)) MA
            FROM (
                SELECT *,
                    LAG(G,1) OVER (PARTITION BY ActorID ORDER BY N) PG,
                    LEAD(G,1) OVER (PARTITION BY ActorID ORDER BY N) NG
                FROM timeline
                ) rg
    )
SELECT * INTO Reordered
FROM ReOrder;
ALTER TABLE Reordered ADD PPP INT
GO
ALTER TABLE Reordered ADD LPP INT
GO
WITH U AS (SELECT N, P, LPP, LAG(PP,1) OVER (PARTITION BY ActorID ORDER BY N) X FROM Reordered)
UPDATE U SET LPP = X FROM U;
WITH U AS (SELECT N, ActorID, P, PG, LPP, PPP, DENSE_RANK() OVER (PARTITION BY N,G ORDER BY PG, LPP) X FROM Reordered)
UPDATE U SET PPP = X FROM U;
GO

SELECT Name, 
    Geometry::STGeomFromText(
        STUFF(LS,1,2,'LINESTRING (') + ')'
        ,0)
        .STBuffer(.1)
        .STUnion(
        Geometry::STGeomFromText('POINT (' + REVERSE(SUBSTRING(REVERSE(LS),1,CHARINDEX(',',REVERSE(LS))-1)) + ')',0).STBuffer(D*.4)
        )
FROM Actor a
    CROSS APPLY (
        SELECT CONCAT(', '
            ,((N*5)-1.2)
                ,' ',(G)+P
            ,', '
            ,((N*5)+1.2)
                ,' ',(G)+P 
            ) AS [text()]
        FROM (
            SELECT ActorID, N,
                CASE WHEN d = 1 THEN
                    ((MA+.0) / (LAG(MG,1) OVER (PARTITION BY ActorID ORDER BY N)+.0)) * 
                    PG * 1.2
                ELSE 
                    ((MA+.0) / (MG+.0)) * 
                    G * 1.2
                END G,
                CASE WHEN d = 1 THEN
                (LAG(PPP,1) OVER (PARTITION BY ActorID ORDER BY N) -((LAG(CP,1) OVER (PARTITION BY ActorID ORDER BY N)-1)/2)) * .2 
                ELSE
                (PPP-((CP-1)/2)) * .2 
                END P
                ,PG
                ,NG
            FROM Reordered
            ) t
        WHERE a.actorid = t.actorid
        ORDER BY N, G
        FOR XML PATH('')
        ) x(LS)
    CROSS APPLY (SELECT MAX(D) d FROM TimeLine dt WHERE dt.ActorID = a.ActorID) d
GO

DROP TABLE Actor;
DROP TABLE Timeline;
DROP TABLE Reordered;

Wynikowa oś czasu wygląda następująco

Mathematica, rozwiązanie referencyjne

Dla porównania udostępniam skrypt Mathematica, który spełnia dokładnie minimalne wymagania, nic więcej, nic więcej.

Oczekuje, że znaki będą listą formatu w pytaniu w charsi wydarzeniach w events.

n = Length@chars;
m = Max@Map[Length, events, {2}];
deaths = {};
Graphics[
 {
  PointSize@Large,
  (
     linePoints = If[Length@# == 3,
         lastPoint = {#[[1]], #[[2]] + #[[3]]/(m + 2)},
         AppendTo[deaths, Point@lastPoint]; lastPoint
         ] & /@ Position[events, #];
     {
      Line@linePoints,
      Text[chars[[#]], linePoints[[1]] - {.5, 0}]
      }
     ) & /@ Range@n,
  deaths
  }
 ]

Jako przykład, oto przykład Parku Jurajskiego z wykorzystaniem typu listy Mathematica:

chars = {"T-Rex", "Raptor", "Raptor", "Raptor", "Malcolm", "Grant", 
   "Sattler", "Gennaro", "Hammond", "Kids", "Muldoon", "Arnold", 
   "Nedry", "Dilophosaurus"};
events = {
   {{1}, {2, 3, 4}, {5}, {6, 7}, {8, 9, 11, 12, 13}, {10}, {14}},
   {{1}, {2, 3, 4}, {5, 8, 6, 7, 9, 10, 11, 12, 13}, {14}},
   {{1}, {2, 3, 4}, {5, 8, 6, 7, 9, 10, 11}, {12, 13}, {14}},
   {{1}, {2, 3, 4}, {5, 8, 6, 7, 10}, {9, 11, 12, 13}, {14}},
   {{1, 5, 8}, {2, 3, 4}, {6, 10}, {7, 9, 11, 12}, {13}, {14}},
   {8},
   {{6, 10}, {1}, {5, 7, 11}, {2, 3, 4}, {9, 12}, {13, 14}},
   {13},
   {{1, 6, 10}, {2, 3, 4}, {5, 7, 11, 9, 12}, {14}},
   {{1}, {6, 10}, {2, 3}, {4, 12}, {5, 7, 11, 9}, {14}},
   {12},
   {{1}, {6, 10}, {2, 3, 11}, {4, 7}, {5, 9}, {14}},
   {11},
   {{1}, {2, 3, 10}, {6, 7}, {4}, {5, 9}, {14}},
   {{1}, {2}, {10, 6, 7}, {4}, {5, 9}, {3}, {14}},
   {{1, 2, 10, 6, 7, 4}, {5, 9}, {3}, {14}},
   {2, 4},
   {{1}, {10, 6, 7, 4, 5, 9}, {3}, {14}}
};

dostaniemy:

(Kliknij, aby zobaczyć większą wersję.)

Że nie wygląda zbyt złe, ale to głównie dlatego, że dane wejściowe są mniej lub bardziej uporządkowane. Jeśli przetasujemy grupy i postacie w każdym zdarzeniu (zachowując tę ​​samą strukturę), mogą się zdarzyć takie rzeczy:

Co jest trochę bałaganu.

Tak jak powiedziałem, spełnia to tylko minimalne wymagania. Nie próbuje znaleźć ładnego układu i nie jest ładny, ale tam właśnie wchodzicie!