Criar gráficos narrativos no estilo xkcd

Em uma das faixas mais icônicas do xkcd, Randall Munroe visualizou as linhas do tempo de vários filmes em gráficos narrativos:

(Clique para uma versão maior.)

Fonte: xkcd No. 657 .

Dada uma especificação da linha do tempo de um filme (ou alguma outra narrativa), você deve gerar esse gráfico. Como é um concurso de popularidade, a resposta com mais votos (líquidos) será vencedora.

Requerimentos mínimos

Para restringir um pouco as especificações, eis o conjunto mínimo de recursos que todas as respostas devem implementar:

• Tome como entrada uma lista de nomes de caracteres, seguida por uma lista de eventos. Cada evento é uma lista de caracteres que estão morrendo ou uma lista de grupos de caracteres (significando quais caracteres estão atualmente juntos). Aqui está um exemplo de como a narrativa do Jurassic Park pode ser codificada:

  ["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]]
  ]
  

  Por exemplo, a primeira linha significa que, no início do gráfico, o T-Rex está sozinho, os três Raptors estão juntos, Malcolm está sozinho, Grant e Sattler estão juntos, etc. O penúltimo evento significa que dois dos Raptors morrem .

  Como exatamente você espera que a entrada seja sua, desde que esse tipo de informação possa ser especificado. Por exemplo, você pode usar qualquer formato de lista conveniente. Você também pode esperar que os personagens nos eventos sejam os nomes completos dos personagens, etc.

  Você pode (mas não precisa) assumir que cada lista de grupos contém cada personagem vivo em exatamente um grupo. No entanto, você não deve assumir que os grupos ou caracteres em um evento estão em uma ordem particularmente conveniente.

• Renderize na tela ou arquivo (como um vetor ou gráfico de varredura) um gráfico que tenha uma linha para cada caractere. Cada linha deve ser rotulada com um nome de caractere no início da linha.

• Para cada evento normal, deve haver, em ordem, uma seção transversal do gráfico na qual os grupos de caracteres se assemelhem claramente à proximidade de suas respectivas linhas.
• Para cada evento de morte, as linhas dos caracteres relevantes devem terminar em um blob visível.
• Você não precisa reproduzir nenhum outro recurso dos enredos de Randall, nem o estilo de desenho dele. Linhas retas com curvas fechadas, todas em preto, sem mais etiquetas e um título é perfeitamente adequado para entrar na competição. Também não é necessário usar o espaço com eficiência - por exemplo, você pode potencialmente simplificar seu algoritmo apenas movendo as linhas para baixo para encontrar outros caracteres, desde que haja uma direção discernível do tempo.

Adicionei uma solução de referência que atende exatamente a esses requisitos mínimos.

Tornando-o bonito

Porém, este é um concurso de popularidade; portanto, além disso, você pode implementar a fantasia que desejar. A adição mais importante é um algoritmo de layout decente, que torna o gráfico mais legível - por exemplo, que facilita as dobras nas linhas e reduz o número de cruzamentos de linhas necessários. Esse é o principal problema algorítmico desse desafio! Os votos decidirão o desempenho do seu algoritmo em manter o gráfico organizado.

Mas aqui estão mais algumas idéias, a maioria delas baseadas nos gráficos de Randall:

Decorações:

• Linhas coloridas.
• Um título para o enredo.
• A linha de rotulagem termina.
• Reencaminhar automaticamente as linhas que passaram por uma seção ocupada.
• Estilo desenhado à mão (ou outro? Como eu disse, não há necessidade de reproduzir o estilo de Randall, se você tiver uma idéia melhor) para linhas e fontes.
• Orientação personalizável do eixo do tempo.

Expressividade adicional:

• Eventos / grupos / mortes nomeados.
• Linhas desaparecendo e reaparecendo.
• Caracteres entrando tarde.
• Destaques que indicam propriedades (transferíveis?) De caracteres (por exemplo, consulte o portador do anel no gráfico LotR).
• Codificação de informações adicionais no eixo de agrupamento (por exemplo, informações geográficas, como no gráfico LotR).
• Viagem no tempo?
• Realidades alternativas?
• Um personagem se transformando em outro?
• Dois caracteres se fundindo? (Um personagem se dividindo?)
• 3D? (Se você realmente for tão longe, verifique se está usando a dimensão adicional para visualizar algo!)
• Quaisquer outras características relevantes, que possam ser úteis para visualizar a narrativa de um filme (ou livro etc.).

Obviamente, muitos deles exigirão informações adicionais, e você poderá aumentar seu formato de entrada conforme necessário, mas documente como os dados podem ser inseridos.

Inclua um ou dois exemplos para mostrar os recursos que você implementou.

Sua solução deve ser capaz de lidar com qualquer entrada válida, mas não há problema se for mais adequada a certos tipos de narrativas do que a outras.

Critérios de votação

Não tenho ilusões de que poderia dizer às pessoas como elas devem gastar seus votos, mas aqui estão algumas diretrizes sugeridas em ordem de importância:

• Respostas negativas que exploram brechas, padrões ou outros, ou codificam um ou mais resultados.
• Não promova respostas que não atendam aos requisitos mínimos (por mais sofisticados que sejam os demais).
• Antes de tudo, vote de novo em algoritmos de layout agradáveis. Isso inclui respostas que não usam muito espaço vertical enquanto minimizam o cruzamento de linhas para manter o gráfico legível ou que conseguem codificar informações adicionais no eixo vertical. Visualizar os agrupamentos sem fazer uma grande bagunça deve ser o foco principal desse desafio, de modo que este continua sendo um concurso de programação com um problema algorítmico interessante no coração.
• Upvote recursos opcionais que adicionam poder expressivo (ou seja, não são apenas decoração pura).
• Por fim, vote com agrado a apresentação.

Python3 com numpy, scipy e matplotlib

editar :

• Tentei manter os grupos na mesma posição relativa entre os eventos, daí a sorted_eventfunção.
• Nova função para calcular a posição y dos caracteres ( coords).
• Todos os eventos vivos são plotados duas vezes agora, para que os personagens se juntem melhor.
• Adicionado legenda e etiqueta de eixos removidos.

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

Não estou feliz com isso como entrada, mas acho que essa pergunta merece pelo menos uma tentativa. Tentarei melhorar esse tempo posteriormente, mas a rotulagem sempre será um problema no SQL. A solução requer o SQL 2012+ e é executada no SSMS (SQL Server Management Studio). A saída está na guia de resultados espaciais.

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

A linha do tempo resultante é semelhante à seguinte

Mathematica, Solução de Referência

Para referência, forneço um script do Mathematica que preenche exatamente os requisitos mínimos, nada mais, nada menos.

Ele espera que os caracteres sejam uma lista do formato na pergunta charse nos eventos em 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
  }
 ]

Como exemplo, aqui está o exemplo do Jurassic Park usando o tipo de lista do 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}}
};

nós conseguiremos:

(Clique para uma versão maior.)

Isso não parece muito ruim, mas é principalmente porque os dados de entrada são mais ou menos ordenados. Se embaralharmos os grupos e os personagens em cada evento (mantendo a mesma estrutura), coisas assim podem acontecer:

O que é um pouco confuso.

Então, como eu disse, isso preenche apenas os requisitos mínimos. Ele não tenta encontrar um layout agradável e não é bonito, mas é aí que vocês entram!