Un seguito tecnico: come abbiamo costruito le mappe di transito generate automaticamente più belle del mondo

di Anton Dubrau

Sei settimane fa, abbiamo lanciato Transit Maps e abbiamo scritto questo post sul blog sul perché abbiamo assunto il compito mastodontico di creare mappe generate automaticamente ma esteticamente gradevoli. Siamo rimasti colpiti dalla reazione pubblica ai nostri sforzi, anche se non del tutto sorpresi dal tempo, dal pensiero e dall'ispirazione necessari per crearli. Oggi manteniamo la nostra promessa di pubblicare un follow-up tecnico di Anton, il nostro wizard di mappatura residente, che spiega in modo molto più dettagliato cosa è andato nella costruzione di queste mappe.

Quando pensi a Transit, potresti pensare a un'interfaccia elegante e colorata. Dato che siamo estremamente particolari nel rendere l'app più bella e utilizzabile possibile, non è una grande sorpresa. Ma l'interfaccia utente non è l'unica cosa di cui ci occupiamo: il nostro team si estende ben oltre i designer esperti e la nostra app è molto più che carina. Sotto la superficie, c'è molta tecnologia "dura" che la guida silenziosamente.

Innanzitutto, la nostra potente qualità di back-end controlla centinaia di feed di dati di transito, corregge automaticamente i dati non funzionanti e segnala i problemi che richiedono un'indagine. Questo sistema ci consente di gestire 350 feed di transito in 125 città con una piccola squadra.

Poi c'è il nostro algoritmo di compressione. Riduce i programmi di transito fino a 100 volte più piccoli di quelli forniti dalle agenzie di transito di file zip. Ciò consente a Transit di scaricare le pianificazioni dell'intera regione dell'utente, archiviare i dati sul dispositivo dell'utente e restituire i risultati della ricerca ... tutto nel tempo necessario ad altre app per richiedere e caricare una singola pianificazione. E mentre i nostri utenti potrebbero ora essere abituati alla velocità della nostra app, quando la funzionalità è stata introdotta per la prima volta, ha ridotto efficacemente i tempi di risposta da diversi secondi a 0,1 secondi. È veloce.

Ma c'è una tecnologia particolare su cui stiamo lavorando da anni. Con nostra grande gioia (e sollievo), l'abbiamo finalmente lanciato quest'estate: mappe di transito generate automaticamente.

Mappe di transito: app di transito (a sinistra), Apple Maps (al centro) e Google Maps (a destra)

L'idea in sé non è affatto nuova: Google ha lanciato le sue mappe di transito quasi sei anni fa. Ma si scopre che è piuttosto il problema da risolvere e Google (anche dopo tutti questi anni) non è ancora in grado di generare mappe di transito molto carine o addirittura molto utili.

Come l'abbiamo gestito? Con sudore, lacrime e pensiero creativo.

1. Forme su una mappa

L'idea di creare mappe generate automaticamente è qualcosa che mi ha affascinato da prima di entrare a far parte dell'App Transit tre anni fa. All'epoca, Google era l'unico attore del settore e, ad essere sinceri, le loro mappe di transito erano piuttosto scadenti. Avevamo appena terminato il suddetto algoritmo di super compressione e ci sentivamo pronti ad affrontare un nuovo problema. Abbiamo pensato, piuttosto ingenuo, che ci sarebbero voluti circa tre mesi. Non sapevamo ...

Il primo passo è stato mostrare i dati di origine su una mappa. Molti dei viaggi nei dati di transito sottostanti contenevano già forme che rappresentavano le rotte intraprese dai veicoli di transito. Se semplicemente disegnassimo tutte le forme definite da tutti i viaggi, otterremmo una sorta di mappa di transito semplicistica:

La nostra tecnologia Mappe di transito, circa novembre 2014

Farlo è stato relativamente semplice: abbiamo creato una pipeline di elaborazione per estrarre le forme dai dati di origine; memorizzato le forme in un formato di scambio dati; assicurato che i dati fossero disponibili per il dispositivo; e ha utilizzato le librerie di mappatura del dispositivo per disegnare un nuovo livello con i dati.

Facile. L'abbiamo messo in funzione nel giro di un paio di settimane.

Ma mentre è vicino, non è una vera mappa di transito. Tutte le linee sono state tracciate una sopra l'altra. Non puoi dire quali linee vanno dove - e l'unica linea visibile era quella tracciata per ultima. Per mappe cartografiche appropriate in cui è possibile seguire le linee con il dito, è necessario che siano disegnate in parallelo e che si intersecino il meno possibile.

2. Corrispondenza con OpenStreetMap

Costruire le nostre mappe con forme ha posto altri problemi: cosa dovremmo fare quando un'agenzia non fornisce dati sulla forma o se un'agenzia fornisce forme molto scadenti? Gli unici dati geografici che avremmo in quei casi sarebbero le posizioni di arresto. Certo, potremmo tracciare linee rette tra le fermate, ma è brutto, disordinato e confuso.

È anche il problema con le mappe di transito di Google. A Berlino, Google effettua collegamenti in linea retta tra fermate; a Londra, usano una sorta di interpolazione spline che non segue le tracce reali; e a Los Angeles, usano le forme fornite dall'agenzia anche se la qualità delle forme è davvero piuttosto negativa.

Google Maps a Berlino (a sinistra) e Londra (a destra)

La cosa divertente è che quando ingrandisci le mappe, vedrai che Google ha spesso dati per i binari ferroviari sottostanti, il che pone la domanda: perché non combinano i binari con i dati di forma? Hanno deciso che non è importante?

Anche se Google potrebbe non pensare che sia importante, certamente lo facciamo. Certo, non abbiamo accesso ai ricchi dati delle mappe sottostanti di Google, ma possiamo usare la cosa migliore successiva: OpenStreetMap (OSM). E grazie alla loro comunità di appassionati di mappe volontari, OSM ha praticamente tutti i binari per le linee ferroviarie di trasporto pubblico che utilizziamo nella nostra app.

I dati ferroviari di OpenStreetMap

Creando una forma lungo la griglia stradale OSM che collega tutti i punti lungo un determinato percorso, potremmo generare le nostre forme di transito! Quindi abbiamo creato un algoritmo di programmazione dinamica che segue le strade o le tracce che potrebbero essere utilizzate dalle linee di transito. L'algoritmo di modellazione prende in considerazione il tipo di veicolo che corre sulla linea e minimizza gli errori di corrispondenza (ovvero le distanze tra la forma generata e le posizioni effettive dei punti di origine).

Ecco un esempio. Nel diagramma seguente, abbiamo un viaggio con tre fermate e nessuna informazione sulla forma. Estraggiamo il set di tracce utilizzato dal viaggio da OSM (linee grigie). Il nostro algoritmo di matching trova quindi una traiettoria (linea nera) che segue l'OSM, riducendo al minimo la sua lunghezza e gli errori agli arresti (e1, e2, e3).

Il processo di abbinamento forma-OSM

È difficile far funzionare questo algoritmo in tutti i casi, quindi a volte dobbiamo fornire parametri per far funzionare linee specifiche. Nel complesso, ci offre forme di alta qualità per tutte le linee di trasporto pubblico di cui abbiamo bisogno oggi e per la maggior parte di quelle di cui avremo bisogno in futuro, anche nei paesi in via di sviluppo in cui OSM è spesso i migliori dati disponibili.

Un esempio che motiva la corrispondenza OSM anche quando le forme sono disponibili e di buona qualità: a Montreal-West, le forme fornite non seguono la traccia (immagine a sinistra), quindi a livello della strada sembra terribile. Dopo l'OSM-matching (a destra), le linee sono molto più fluide.

3. Elaborazione in Pixel Space: Skeletonization

OSM ci ha dato le forme, ma le linee erano ancora tracciate una sopra l'altra. Le mappe di transito reali hanno linee tracciate in parallelo. Ciò che dovevamo fare era identificare segmenti comuni, dove viaggiano sulla stessa strada, e quindi "agganciare" quelle linee insieme.

Quindi, come fa Google? Sembrano calcolare segmenti condivisi guardando le fermate. Finché due linee condividono le stesse fermate, vengono "spezzate" insieme. Ma quando la fermata successiva non è condivisa, le righe "unsnap":

Le linee di Google dimenticano di conoscersi immediatamente all'ultima fermata in cui si fermano insieme.

Ma non è così che viaggiano davvero treni e autobus! Le linee rimangono insieme per una certa distanza prima di divergere. Ciò di cui avevamo bisogno era un algoritmo che trovasse dove le linee iniziassero a ramificarsi nella vita reale.

Abbiamo cercato di calcolare le separazioni del percorso nello spazio vettoriale, che all'inizio sembrava semplice: prendere due linee che viaggiano strettamente insieme e quindi trovare la linea centrale del segmento condiviso. Ciò si è rivelato sorprendentemente complicato, tuttavia, mentre continuavamo a imbatterci in semplici esempi che avrebbero rotto il nostro algoritmo. Un piccolo anello lungo il percorso avrebbe gettato via la linea centrale all'infinito e dovevamo anche occuparci di più linee, più rami, diversi schemi di arresto ...

Dopo due mesi passati a battere il nostro cervello contro le nostre tastiere, abbiamo finalmente gettato la spugna. Non siamo riusciti a trovare una soluzione generale stabile che funzionasse in modo affidabile fino a quando ...

Spazio pixel in soccorso!

Invece di elaborare le linee nello spazio vettoriale, abbiamo deciso di provare qualcosa di folle. Abbiamo usato lo spazio dei pixel.

Di solito l'elaborazione basata su pixel viene eseguita per dati basati su immagini. È molto insolito per l'elaborazione GIS, perché con una risoluzione di 1px / metro, la nostra immagine sarebbe di 64 terabyte. Di questi tempi la memoria è economica ... ma non così economica!

Come l'abbiamo fatto? Abbiamo implementato una speciale libreria di immagini sparse in grado di gestire queste immagini monocromatiche molto grandi con relativamente poche aree bianche.

Abbiamo quindi creato un algoritmo per disegnare forme di transito su una gigantesca tela in bianco e nero che rappresenta il mondo intero, dove ogni pixel equivale a un metro quadrato. Ogni linea è stata disegnata spessa sulla tela, quindi ovunque le linee fossero vicine, i loro pixel si fondevano insieme.

Una volta tracciate tutte le linee, abbiamo usato un processo di "scheletratura" per assottigliare le linee in successione fino a quando ognuna era spessa solo un pixel. Quindi, mentre le linee non venivano più unite, rimanevano collegate, mantenendo la stessa topologia. Queste linee sottili rappresentano il punto in cui le linee di transito viaggiano insieme e rivelano la struttura della rete.

Il bianco rappresenta le linee di transito disegnate. Lo

Sebbene ora disponessimo delle linee centrali della rete, avevamo distrutto più informazioni di quante ne avessimo acquisite. Ciò che avevamo ora erano un mucchio di pixel che indicavano lo scheletro, il che significava che sapevamo che ogni linea doveva percorrere questo scheletro, ma dovevamo ancora capire quali linee stavano viaggiando dove.

Usando lo scheletro, ora abbiamo ricostruito le linee, al contrario delle forme che precedentemente avevamo. Abbiamo quindi elaborato la rete risultante per eliminare i problemi introdotti dalla scheletrizzazione.

Questo passaggio è stato lungo e noioso. Complessivamente, il disegno, la scheletrizzazione, la costruzione di reti e la rimozione di problemi tecnici hanno richiesto circa sei mesi per svilupparsi. (Tanto per aver fatto tutto in tre!)

Ma i risultati finali sono stati soddisfacenti. Avevamo una rappresentazione interna di linee che viaggiano insieme e divergono. Sembrava così:

Quando abbiamo reso le linee in parallelo, abbiamo ottenuto questo:

Successo!

Abbastanza buono per una versione 1. Molto meglio di Google, visto che puoi più o meno capire dove sta andando ogni linea. Eravamo pronti a lanciare Mappe di transito! E poi ... è successo Apple Maps.

Nell'estate del 2015, dopo aver lavorato sulle nostre mappe per la maggior parte dell'anno, eravamo finalmente pronti a rilasciare la nostra prima versione di Transit Maps. Quindi Apple ha lanciato le sue mappe di transito ed erano davvero carine.

Le belle mappe di transito di Apple

Hanno immediatamente alzato l'asticella per come dovrebbero apparire le mappe di transito. Nei nostri disegni e progetti, l'obiettivo finale era qualcosa di simile (o migliore) a quello che Apple ha successivamente rilasciato, ma stavamo pianificando di arrivarci dopo aver rilasciato la nostra versione 1.

Rispetto ad Apple, la nostra versione 1 proposta era un po 'mediocre. Il nostro Designer-CEO ha decretato che battere Google non era abbastanza buono - dovevamo anche giocare almeno nella stessa lega di Apple.

Dopo un esame più attento, abbiamo ipotizzato che Apple stesse disegnando le loro mappe manualmente. C'erano enormi ritardi tra il rilascio di nuove città e c'era qualcosa di strano nel modo in cui le mappe apparivano - come se fossero state disegnate da umani, non da computer. Ciò significava che, sebbene le nostre mappe non fossero altrettanto belle, il nostro algoritmo era ancora più avanti delle loro.

A questo punto, sapevamo anche che la parte difficile era dietro di noi. Avevamo escogitato una rete che ci avrebbe permesso di tracciare linee in parallelo. Ora, tutto ciò che dovevamo fare era farlo sembrare buono.

4. Ordinamento linea di transito mediante programmazione lineare intera

Prima di pubblicare le nostre mappe, dovevamo sbarazzarci del brutto e inutile incrocio di linee, che le stava trasformando in un orribile pasticcio di spaghetti.

Se potessimo ordinare le linee per ridurre al minimo il disordine visivo vicino alle intersezioni, avremmo una mappa pubblicabile. Per fare questo, abbiamo dovuto decidere quali linee sarebbero andate a sinistra e quali sarebbero andate a destra, al fine di minimizzare i loro incroci.

Google ha (e ha ancora) un problema simile - tranne che le sue linee si incrociano anche quando ci sono solo fermate e senza incroci.

Oh, vieni su Google! Le linee dovrebbero rimanere organizzate.

Per noi, l'attraversamento incrociato è avvenuto solo dove le linee si sono effettivamente unite e divergenti, quindi stavamo già facendo meglio dell'algoritmo di Google. Questo perché stavamo archiviando sezioni condivise in base alla geografia.

Quindi come ci siamo liberati degli spaghetti? Innanzitutto, abbiamo provato una soluzione euristica - ordinamento delle linee in base al punto in cui terminano - ma ciò spesso falliva, funzionando in alcuni punti, ma non in altri.

Per migliorare la soluzione euristica, abbiamo creato un modello matematico che "segnerebbe" un determinato ordine di linee, penalizzando l'attraversamento delle linee, così come altri disordini visivi.

Diversi possibili scenari di intersezione, che segnano le fonti di penalità usando i cerchi rossi

Come ci si potrebbe aspettare, evitare un incrocio in un punto della mappa potrebbe crearne un altro altrove. Tutto è connesso! Quindi cosa abbiamo fatto? Abbiamo trovato l'ordinamento di linee con il punteggio di penalità globale più basso.

La programmazione lineare lineare è stata ciò che ci ha permesso di esplorare tutte le possibilità e trovare una soluzione che minimizzasse globalmente la funzione di penalità. Ma il tempo di elaborazione per la programmazione lineare intera è esponenziale nella dimensione del problema: la risoluzione di un problema può richiedere un secondo; un altro problema più difficile può richiedere un anno! Ciò ha reso rischioso l'utilizzo, anche nella pre-elaborazione "offline" all'interno del back-end.

Eravamo preoccupati L'elaborazione dei dati di Chicago ci ha impiegato ore. Un'area più ampia come il corridoio nord-est (da Boston a Washington) potrebbe richiedere settimane! Fortunatamente, abbiamo trovato un diverso piano di attacco: quello che ha permesso al risolutore di programmazione lineare intera di esplorare lo spazio problematico in modo più efficiente e di trovare soluzioni ottimali più velocemente. Ciò che prima richiedeva un'ora, ora impiegava 0,2 secondi.

Vedere l'ottimizzazione come questa in azione è sorprendente: quando vedi che l'algoritmo prende decisioni, è come assistere a un brillante matematico che risolve senza problemi i problemi con le soluzioni più chiare e concise.

Ordinamento prima / dopo la riga

Con le altre fasi di elaborazione già completate nella pre-elaborazione sul server, i dati erano ora archiviati in file binari e inviati al dispositivo per il rendering effettivo delle mappe a qualsiasi livello di zoom desiderato.

5. Arrotondamento delle linee Circle-Arc

Tuttavia, non avevamo ancora finito. Le mappe di transito schematiche disegnate a mano non assomigliano ancora alle mappe mostrate sopra. Le loro linee sono ben arrotondate con transizioni fluide agli incroci. Volevamo che le nostre mappe avessero un aspetto arrotondato simile.

Quando le linee tracciavano dietro gli angoli, volevamo che rimanessero perfettamente parallele, anche in casi potenzialmente degenerativi, come a Chicago. Lì, un gran numero di linee viaggiano insieme attorno a curve nette, quindi disegnandole in parallelo si potrebbe formare un raggruppamento di linee all'interno della curva.

Di solito l'arrotondamento viene eseguito utilizzando curve di Bezier, che sembrano allentarsi nelle curve. Ma per rimanere fedeli all'aspetto delle mappe schematiche del transito, le curve di Bezier non avevano ragione. Le mappe di transito hanno linee rette che cadono bruscamente in segmenti di arco circolare. Quindi abbiamo usato segmenti di arco per arrotondare.

Inoltre, diversamente dalle curve di Bezier, qualsiasi linea parallela a un arco circolare è essa stessa un arco circolare. Finché il raggio è abbastanza grande, ci è stato garantito di non avere casi degenerativi.

Abbiamo escogitato un algoritmo personalizzato che, data una forma, avrebbe rimosso e aggiunto punti per arrotondarlo usando segmenti di arco circolare. Garantisce un raggio minimo dato semplificando la geometria, se necessario. Il raggio minimo dipende dalla larghezza totale di tutte le linee parallele.

La forma risultante è liscia. È interamente composto da linee rette e segmenti di arco, il che significa che possiamo sempre tracciare linee in parallelo senza artefatti o casi degenerativi.

Questo approccio ci ha dato qualcosa del genere:

L'arrotondamento avviene solo lungo segmenti condivisi. Potresti anche notare che abbiamo rimosso tutte le intersezioni. Gestire le intersezioni era un grosso problema perché dovevamo garantire che ogni linea continuasse da un segmento all'altro e si collegasse correttamente. Abbiamo anche usato l'algoritmo di generazione dell'arco per avere lo stesso aspetto arrotondato. Ecco il risultato finale:

Abbastanza grande, vero? Ma mentre erano belli ... sembravano ancora stranamente nudi. Questo perché mancavano fermate.

Quindi abbiamo deciso di non rilasciare ancora la versione e aggiungere un ultimo passaggio.

6. Aggiunta di fermate

L'aggiunta di fermate potrebbe sembrare semplice, ma in realtà richiede una discreta quantità di elaborazione per propagare le informazioni sulla fermata attraverso la lunga pipeline che abbiamo creato.

Abbiamo anche riscontrato molti casi in cui più fermate nei dati corrispondevano effettivamente a una singola stazione fisica, quindi dovevamo comprimerle in una fermata.

Ecco cosa abbiamo fatto. Per le fermate con più linee, abbiamo disegnato una barra bianca con un contorno nero (per il contrasto) su tutte le linee. Per le fermate su una sola linea, abbiamo disegnato un semplice cerchio usando il colore di quella particolare linea di transito. Abbiamo anche aggiunto un overlay bianco per ridurre il contrasto del livello della mappa sottostante. Questo è il risultato finale:

Per consentire agli utenti di attivare e disattivare le linee in modo selettivo dalla pagina delle impostazioni delle nostre app, abbiamo deciso che l'arrotondamento, nonché alcuni arresti e rendering dovrebbero essere eseguiti sul dispositivo. Quindi a New York City, puoi disabilitare tutte le linee di transito basate sul New Jersey (o tutte le linee di New York se vivi nel New Jersey). Con così tante linee di transito in determinate aree, questo consente agli utenti di creare mappe completamente personalizzate.

Nota come le linee più recenti in base a quale linea sono attive e in che modo l'arresto cambia colore.

Conclusione

È così che l'abbiamo fatto. Certo, l'implementazione di mappe di transito generate automaticamente ha richiesto molto lavoro, ma ne è valsa la pena. Le nostre mappe sono molto più potenti dei PDF che sei abituato a ottenere dalle agenzie, non importa quelli di carta che pieghi e blocchi nel tuo portafoglio. Quali sono le principali differenze?

Le nostre mappe di transito sono scalabili, quindi possiamo facilmente aggiungere nuove città nello stesso stile visivo, ovunque nel mondo ci espandiamo al prossimo. Sono personalizzabili, quindi gli utenti possono attivare / disattivare reti e modalità per creare mappe di transito personalizzate. E sono anche contestuali: a differenza di un PDF di una mappa di agenzia, le nostre mappe incorporano la tua posizione dandoti un'idea di dove sei rispetto alle linee vicine e regolando l'aspetto in base al livello di zoom.

E in definitiva, le nostre mappe schematiche di transito forniscono molto più delle semplici informazioni di base sui sistemi di transito. Sono emblematici delle città stesse: importanti opere d'arte funzionale che collegano le persone ai loro ambienti. Vogliamo aiutare a costruire quella connessione e crediamo che le nostre nuove mappe di transito facciano proprio questo.

Siamo entusiasti di continuare a migliorare, ma siamo soddisfatti di ciò che abbiamo realizzato finora. Abbiamo lanciato con 55 città. La risposta al nostro post sul blog, confrontando le nostre mappe con Google e quelle di Apple, è stata incredibilmente positiva. Per il team di backend, è bello che le persone vedano e apprezzino il lavoro e lo sforzo che dedichiamo a ciò che guida l'esperienza dell'app. Ci motiva a continuare a spingere ulteriormente la nostra tecnologia.

Oltre a ciò, abbiamo ancora molti problemi "difficili" da risolvere. Continueremo a lavorare sotto il cofano, non solo per avere l'app più carina con la migliore interfaccia utente, ma l'app di transito più funzionale, potente e accurata là fuori.

Vuoi giocare con le nostre mappe?
Puoi ottenere Transit gratuitamente su App Store e Google Play. Oppure scopri di più sull'azienda sul nostro sito web.

Hai voglia di affrontare sfide come questa per vivere? Stiamo assumendo!