Che struttura di dati usa Google per memorizzare le mappe offline?

Ho smesso di lavorare alla mia tesi per scrivere una risposta, dato che questa domanda ha suscitato il mio interesse :)

Non ho idea di come Google Maps memorizzi le sue mappe offline, ma conoscendo Google, comporta qualche metodo tremendamente intelligente per comprimere quei dati. Non sono sicuro di essere d'accordo con il tuo argomento che un "grafico puro" non può definire le strade. Sto per dare la mia ipotesi completamente ignorante su come si potrebbe andare a codificare i dati di navigazione.

Prova a immaginare cosa sia realmente una strada ai fini della navigazione. Si riduce a una serie di waypoint geografici collegati, con un certo peso tra ciascuno di essi. Questo peso è correlato a un costo di viaggio (distanza combinata con una velocità stimata). Ogni segmento di strada tra i waypoint ha una forma. Questa forma è fondamentalmente solo una combinazione di linee rette e curve, ma niente che sia impossibile da codificare.

Si possono anche combinare curve e linee tra i waypoint di navigazione con inter-waypoint, o un waypoint invisibile che esiste per modellare la forma della strada ma non interagisce con la pianificazione del percorso.

Una curva può essere rappresentata dalla funzione continua di 2° ordine:

[math]y = ax^2 + bx + c[/math]

Non abbiamo bisogno della costante c per il fatto che la nostra funzione inizia sempre su un waypoint noto. Pertanto, abbiamo solo bisogno di memorizzare 2 costanti per codificare una curva!

Per quanto riguarda i segmenti di strada che sono linee rette, non abbiamo bisogno di memorizzare nulla! Conosciamo già il punto iniziale e finale.

Quando codifichi le tue strade come funzioni (linea retta o curva), puoi utilizzare un approccio simile alla grafica vettoriale per disegnare una strada a qualsiasi livello di dettaglio tu voglia.

Diciamo che quando una mappa viene scaricata, Google Maps cerca di risparmiare più spazio possibile riducendo gli intervalli di indirizzi simili ad una singola entità. Si ottiene ancora l'isolato corretto e il lato della strada, ma non la posizione precisa. Questo potrebbe probabilmente ridurre la memorizzazione delle mappe delle città dense di un fattore 3 o più se si considera quante cose possono trovarsi nello stesso isolato.

Sarebbe anche necessario codificare il numero di corsie di ogni strada, e la natura di ogni intersezione rispetto al numero di corsie di svolta, rotatoria o semaforo, e così via.

Per quanto riguarda le località stesse, non sono sicuro che ci sia molto che si possa fare per ridurre la dimensione della memoria. Dovete memorizzare il loro nome, l'indirizzo e le coordinate globali. Probabilmente puoi codificare la dimensione e la forma dell'edificio renderizzato sullo schermo, dato che la maggior parte degli edifici sono rappresentati solo come scatole bianche.

Hai anche bisogno di avere caratteristiche dell'acqua sulla tua mappa! Hai bisogno di un metodo per tracciare quale spazio è acqua e quale terra. Un modo per farlo è con un'immagine binaria. Avete una "maschera d'acqua" che denota il valore 1 = terra e 0 = acqua per ogni pixel. Potete poi usare qualche tecnica di compressione dell'immagine per codificare i "blob" d'acqua. Le tecniche di levigatura potrebbero aiutare a rendere la caratteristica dell'acqua a livelli più piccoli di dettaglio.

Così ci siamo. Questo metodo codificherebbe molto bene le autostrade rade e dritte in mezzo al nulla, e male le strade curve disarticolate con molti piccoli punti d'acqua. Meno complessa è la forma della strada, meno dati devono essere salvati. Sono abbastanza curioso che potrei provare a mettere insieme un esempio di questo solo per vedere quanti dati potrebbero essere salvati rispetto a un'immagine dettagliata dell'intera area.