Algoritmo per le mappe (metro) schematizzare

Question

Questa è una possibilità remota, ma ho pensato che avrei potuto provare prima di iniziare il lavoro sporco.

Ho un progetto per costruire un programma che sarà, per le stazioni di ingresso definite (vertici) e linee (bordi), cioè, di una vera e propria mappa di un mezzo di trasporto pubblico, schematizzare una determinata mappa in una mappa della metropolitana. Ho fatto qualche ricerca sul problema ed è un problema NP-completo equivalente al problema 3-SAT. Ho anche alcune idee teoriche su come generare una tale mappa, ma non sono sufficientemente dettagliate.

Quello che sto cercando è qualsiasi altra soluzione esistente di questo problema, una sorta di pseudo-codice, qualche reale il codice a (quasi) qualsiasi altro linguaggio di programmazione, ecc, qualsiasi cosa che possa ridurre il tempo ho bisogno di spendere lavorare su lo stesso algoritmo, che in cambio darmi più tempo per lavorare su altri aspetti dell'applicazione.

Se qualcuno ha mai visto niente che mi può aiutare, io apprezzo molto.

Answer 1

Se Google per "Metro Map problema layout" e "mappa della metropolitana linea crossing" troverete un sacco di riferimenti, dal momento che è stato studiato in modo molto attivo negli ultimi 10 anni.

Il problema sembra non banale a tutti, e traducendo le caratteristiche "artistiche" a vincoli matematici è apparentemente uno dei compiti più difficili.

In ogni caso qui ci sono tre pubblicazioni che ho trovato interessante per iniziare con (tra molti, molti altri):

Metro Map layout mediante Multicriteri Ottimizzazione

linea Crossing Minimizzazione sulle Mappe Metro

La Metro Map layout Problema

HTH!

Answer 2

La ricerca che è simile al tuo argomento: http://graphics.stanford.edu/papers/routemaps/

Answer 3

Questo è solo qualche suggerimento con handwaving -. Prendere con un pizzico di sale

La mia idea di una mappa "metro" è quella in cui le linee tendono a una delle otto direzioni cardinali e le stazioni sono distanziati regolarmente.

sto supponendo che si sta tentando di convertire un insieme di coordinate reali in coordinate "metro".

Vorrei iniziare con il percorso principale (ad esempio, un ciclo di città), quindi in modo incrementale aggiungere altri itinerari in ordine di importanza.

Per ogni percorso che si desidera trovare l'approssimazione più vicina che utilizza il minor numero di linee rette che viaggiano nelle otto direzioni cardinali. Si potrebbe farlo iniziando con il rettangolo di selezione per le quote reali, divisione che in una griglia, poi trovare un percorso "metro" da piazza della griglia a griglia quadrata, poi successivamente raffinazione questa strada per ridurre il numero di curve senza distorcere la mappa troppo e senza introdurre incroci con altri percorsi se possibile.

Dopo aver fatto ciò, scala ogni riga in modo che le stazioni consecutive sono alla stessa distanza nella vista "metro".

La mia ipotesi è che si sarà ancora desidera supportare ritocco manuale del risultato.

In bocca al lupo!

Answer 4

Si sente come un problema di pianificazione. Sembra che il tuo vincoli rigidi sono:

• Ogni stazione deve essere su un punto. A punti sono su una griglia con una distanza di X tra i punti (mi piacerebbe fare questo statico su 2 cm)

• Ci non dovrebbe essere 2 stazioni sullo stesso posto

• Non ci dovrebbe essere spazio sufficiente per attirare l'etichetta stazione. Notare che l'etichetta può essere assegnato direzioni diverse dal punto a cui è assegnata la stazione.

• Non ci dovrebbe essere spazio sufficiente per disegnare le linee della metropolitana.

Sembra che il tuo vincoli soft sono:

• Per ogni stazione, minimizzare la realtà geografica distanza di posizione al punto assegnato alla stazione.

Poi buttare qualcosa come Drools Planner su di esso, ecco un esempio di vincoli duri e molli per infermiere rostering .