Mi è stato chiesto questo in un test di intervista. Ho fatto bene sul test ma non sapevo abbastanza per rispondere a questa domanda. Sono curioso di sapere quali strutture dati posso usare per interrogare rapidamente i dati.
Fondamentalmente l'idea è che ci sarebbero sezioni stradali (linee, costituite da punti) memorizzate in una sorta di struttura dati. Dovrebbe essere veloce per interrogare quali tratti (o punti) della strada si trovano entro una certa distanza da un punto (raggio).
Il modo tipico per archiviare i dati geografici è con una struttura di dati spaziali come un albero R (o qualche variante, come albero R +, albero R *, ecc.). Ecco come i tipi di dati geografici vengono normalmente implementati in RDBMS con supporto GIS. (So che SQL Server 2008 e PostGIS di Microsoft utilizzano R-tree per i tipi geografici.) Rispondono a tutti i requisiti di base che hai descritto e supportano banalmente intersezione, posizione, distanza e altri tipi di query.
A seconda del tipo di dati, si possono trovare anche oggetti come alberi di kD, alberi quadrangolari, alberi, gerarchie di volume di delimitazione (inclusi alberi di delimitazione allineati agli assi), ecc. Questo è in realtà molto più comune nei giochi 3D, dal momento che le dimensioni e la forma di un oggetto sono più rilevanti per le query di intersezione. Sono usati meno spesso per i GIS rispetto agli alberi R.
Diversi tipi di operazioni sui dati delle mappe richiederanno diversi formati di archiviazione per risultati ottimali. Prendi in considerazione, ad esempio, i seguenti tre compiti:
Le differenze nei requisiti sono sufficientemente grandi che, a meno che non sia necessario adeguare le modifiche "in tempo reale" alla mappa, sarà probabilmente meglio memorizzare tre copie separate dei dati, ognuna ottimizzata per una delle attività sopra elencate. -than cercando di trovare un formato in grado di gestire bene tutte e tre le attività.
Leggi altre domande sui tag data-structures algorithms