Memoria e compressione di latitudine / longitudine in C

https://stackoverflow.com/questions/1220377

10-07-2019
|

Domanda

Qualcuno conosce la rappresentazione più efficiente per coordinate lat / long? Il livello di precisione dovrebbe essere sufficiente per i dispositivi GPS di consumo.

La maggior parte delle implementazioni sembrano usare double per ogni unità, ma sospetto che un float o un formato a virgola fissa dovrebbero essere sufficienti. Sarei curioso di sapere da chiunque abbia cercato di comprimere o archiviare grandi array di questi valori.

EDIT:

In altre parole, qual è l'accuratezza minima richiesta per rappresentare lat / long per un dispositivo di livello consumer?

Soluzione

Personalmente userei una rappresentazione decimale a virgola fissa a 32 bit, dividendola per 1.000.000 secondo la risposta di Evan e i miei commenti.

Tuttavia, se lo spazio è davvero un premio, ecco alcune idee aggiuntive:

È possibile utilizzare una rappresentazione in virgola fissa a 26 bit sul filo. Ciò richiederà il marshalling e il non marshalling della latitudine e della longitudine in una vasta gamma di byte, ma ti farà risparmiare 12 bit per ogni posizione rispetto alla rappresentazione del valore a 32 bit - quasi un risparmio del 19%, quindi potrebbe valere la pena.
Potresti trarre vantaggio dal fatto che i valori di longitudine richiedono meno precisione man mano che ti avvicini ai poli - hanno solo bisogno di 26 bit all'equatore. Quindi potresti scrivere uno schema in cui il numero di bit utilizzati per codificare la longitudine dipende dal valore della latitudine.
Se i tuoi dati hanno altri attributi comprimibili - diciamo, tutti i punti sono generalmente abbastanza vicini tra loro - potresti trarne uno specifico vantaggio, come usare uno schema di codifica delta (dove ogni punto diverso dal primo può essere codificato come delta dall'ultimo punto).

Altri suggerimenti

La circonferenza della Terra è di ca. 40.000 km o 24900 miglia.

È necessaria una precisione di un metro (3 piedi) per essere in grado di superare la precisione dei gps di un ordine di grandezza.

Pertanto è necessario precisare per memorizzare 40.000.000 di valori diversi. Sono almeno 26 bit di informazioni. Un float o int a 32 bit andrà bene.

EDIT: aggiunto alcuni punti dai commenti, i valori a 32 bit dovrebbero essere in grado di offrire una precisione sufficiente.

Vorrei usare una rappresentazione in virgola fissa a 32 bit. Se i valori sono:

42.915512 , -99.521654 Vorrei memorizzare i valori * 100000 in int32_t 's (possono essere negativi).

int32_t lat = 42915512;
int32_t lon = -99521654;

Questo è un buon compromesso tra punti decimali semplici e precisi ( 5 è generalmente abbastanza buono, puoi sempre aumentarlo fino a 1000000 per ottenere 6 se necessario).

Per mostrare all'utente, fai ciò che caf suggerisce:

... per mostrare all'utente - usa intero divide e modulo, ad es. printf (" Lat = % d.% 06d \ n " ;, lat / 1000000, abs (lat)% 1000000)

Questi saranno anche comparabili / ordinabili in modo efficiente poiché il relativo ordine sarà preservato.

EDIT: un ulteriore vantaggio è che può essere inviato su una rete o archiviato su disco in un formato binario in modo portatile.

I galleggianti sarebbero molto più che sufficienti per memorizzare le coordinate GPS, anche se i dispositivi GPS di livello consumer avessero un livello vicino all'accuratezza richiesta per loro. Se non ritieni che ciò sia vero, prova questi due semplici esperimenti:

Prendi due o più dispositivi GPS in un punto su un campo da qualche parte e annota le coordinate misurate da ciascun dispositivo. Torna all'interno e traccia i punti di ciascun dispositivo su una mappa (penso che Google abbia qualcosa che lo fa per te). Sarai sorpreso di quanto siano distanti i punti (anche se tutti dovrebbero misurare esattamente lo stesso punto).
Prendi il tuo dispositivo (presumibilmente) più accurato e posizionalo in un punto in cui possa ottenere una correzione satellitare ma non vi farà piovere, e registra una serie di misurazioni effettuate nell'arco di un paio di giorni. Traccia tutte le letture (come nel n. 1). Ancora una volta, rimarrai sorpreso dal modo in cui i punti (che dovrebbero essere tutti uguali o quasi uguali) vagano su tutta la mappa, a volte fino a duecento piedi.

Sto scrivendo applicazioni per PDA abilitati per GPS da anni e lo ho verificato più volte per i clienti dubbiosi (ho anche vinto le scommesse in questo modo). Esistono dispositivi GPS di qualità superiore che ottengono una precisione maggiore di questa, ma la migliore precisione si ottiene con chipset più costosi e i dispositivi vengono lasciati in un punto per giorni o addirittura settimane, con le letture medie nel tempo.

Un float a quattro byte è molto più preciso dei dispositivi stessi . Ovviamente non ti farebbe male usare un doppio, purché il fattore 2X non sia un problema per te.

23 bit di precisione a 179 gradi di longitudine offrono una precisione inferiore a 10 metri, che è il massimo che i normali dispositivi GPS offrono. All'equatore:

% gps distance "0.0, 179.0" "0.0, $((179 * (1 + 2**-23)))"
From 0.0, 179.0 to 0.0, 179.00002133846283 is 7.79 feet E
From 0.0, 179.0 to 0.0, 179.00002133846283 is 2.38 meters E

Quindi un numero IEEE 754 a virgola mobile a precisione singola, noto al compilatore C come float , sarà semplicemente adeguato per la rappresentazione. Attenzione all'utilizzo di float per calcoli estesi! L'errore di arrotondamento potrebbe consumare il tuo pranzo. Consultare un analista numerico.

Nel formato mappa IMG di Garmin, memorizzano le coordinate all'interno dei riquadri di delimitazione utilizzando i float per impostare i bordi delle caselle. I coordini all'interno delle caselle sono definiti utilizzando un numero variabile di bit che sono semplicemente lineari tra i valori minimo e massimo in base alla precisione richiesta.

Ad esempio: minlat = 49.0, maxlat = 50.0, minlon = 122.0, maxlon = 123.0, numero di bit = 16

Quindi un valore di:
32768.32768 verrebbe convertito in 49.5, 122.5
16384,0 sarebbe 49,25, 122,0

Se hai bisogno di meno precisione, lo stesso output potrebbe essere generato con un numero di bit = 4
8,8 verrebbe convertito in 49.5, 122.5
4,0 sarebbe 49,25, 122,0

Se si stanno memorizzando grandi matrici di questi valori, ci sono alcuni semplici trucchi se si esegue una compressione delta e si memorizzano delta, è possibile ridurre notevolmente le dimensioni di un flusso di dati. Puoi eseguire delta da un punto chiave "

K D D D D D D D D D D K D D D D ...

k + d ti porta a qualsiasi punto d

I delta fanno tutti riferimento alla K precedente, quindi per ricostruire qualsiasi punto, hai bisogno di una K e una D

oppure puoi fare delta incrimentali

K I I I I I I I I I I K K

Questo può richiedere più somme per arrivare alla posizione desiderata. ma i dati sono complessivamente più piccoli. Quindi ricostituire

k + i + i + i per arrivare al 4 ° punto

Finalmente puoi combinare entrambi

K D I I I D I I I D I I I K

Questo è come mpeg-2 con frame IPB, ma in questo modo non sei mai più di 4 somme in qualsiasi posizione e ottieni alcuni dei vantaggi di Delta e Incrimental Compression.

Puoi racchiudere i valori di latitudine e longitudine in un singolo numero intero a 32 bit con una risoluzione nella peggiore delle ipotesi ~ 2,4 metri / pixel (all'equatore) se si utilizza un sistema di piastrellatura ricorsivo. Utilizzando due bit per livello, è possibile memorizzare 16 livelli in 32 bit. Puoi avere un'idea di come funzionerebbe guardando questo articolo sulla Piastrellatura di Virtual Earth sistema . Questo usa Mercator, quindi ti darebbe problemi per i poli. Potresti invece utilizzare una proiezione diversa e ottenere comunque risultati molto simili.

Questo può anche essere usato per un filtro approssimativo per trovare punti all'interno di una determinata tessera padre poiché i primi N bit saranno gli stessi (e quindi la ricerca diventa mascheramento di bit).

Supponendo che la terra sia una sfera perfetta (non è, ma abbastanza vicina) con un raggio & # 8216; R & # 8217; di 3959 miglia (o & # 215; 5280 piedi / mi = 20903520 ft), la circonferenza è 131340690 piedi (usando 2 & # 215; PI & # 215; R).

360 gradi di longitudine coprono 131340690 piedi. 180 gradi di latitudine coprono 65670345 piedi.

Se si desidera memorizzare lat / lng fino a una precisione di 3 piedi, è necessario essere in grado di memorizzare i valori di latitudine 43780230 (131340690/3) e i valori di latitudine 21890115 (65670345/3). 43780230 richiede 25.38 bit (log (43780230) / log (2)) per memorizzare e 21890115 richiede 24.38 bit (log (21890115) / log (2)) per memorizzare & # 8211; o poco meno di 50 bit (o 6,25 byte).

Quindi diventa ovvia la domanda, se si desidera memorizzare latitudine e longitudine in soli 6 byte, quale sarà l'accuratezza? Bene, 6 byte è 48 bit. Ciò significa 23,5 bit per la latitudine e 24,5 bit per la longitudine (la longitudine ha il doppio dei valori, che è solo un bit e 24,5-23,5 = 1 bit). Quindi 23,5 bit consente di rappresentare un numero compreso tra 0 e 11863282 (valori 11863283). E 65670345 piedi divisi per 11863283 valori sono 5,53 piedi (e lo stesso valore di precisione per la longitudine).

THE BOTTOM LINE: Quindi, se riesci a vivere con una precisione di 5,5 piedi sia per la latitudine che per la longitudine, puoi comprimere entrambi i valori in soli sei byte.

* UNA NOTA LATERALE: per quanto riguarda i commenti secondo cui latitudine e longitudine sono orribili per la memorizzazione delle informazioni di posizione attorno a una sfera (perché ci sono meno informazioni da memorizzare ai poli) & # 8211; bene, quei commenti non resistono alla matematica! Cerchiamo di capirlo. Diciamo che vogliamo progettare un nuovo sistema perfetto in grado di registrare e posizionare un paletto nel terreno al centro di ogni piede quadrato della terra. La superficie della terra (con una R di 3959 miglia; formula per la superficie di una sfera) è 5490965469267303 SQ FT & # 8211; che molte puntate richiedono 52.29 bit per rappresentare. Ora il sistema di latitudine e longitudine esistente utilizza un sistema rettangolare. La larghezza del rettangolo è la circonferenza della terra e l'altezza del rettangolo è 1/2 della circonferenza) & # 8211; che è 131340690 * 65670345 (vedi molto sopra) o 8625188424838050 SQ FT & # 8211; che richiede 52.94 bit per rappresentare (questo sistema posiziona & # 8216; troppe & # 8217; picchetti nel terreno attorno ai poli). Quindi, la risposta scioccante è che sia il nuovo sistema perfetto, sia il vecchio sistema lat / lng, ENTRAMBI richiederebbero 53 bit effettivi per memorizzare una singola posizione sulla terra, con una precisione fino a 1 piede!

Sono sorpreso che nessuno abbia pubblicato il fatto che long / lat è un modo terribile per archiviare dati su una sfera (qualcuno ha menzionato che la longitudine richiede meno precisione vicino ai poli).

Fondamentalmente è possibile memorizzare la posizione dei dati come coordinate X e Y in metri. Immagina un cubo attorno alla terra che si adatta esattamente (haha ok quasi si adatta). Hai solo bisogno di memorizzare le posizioni X e Y, non tutte e 3 le coordinate, perché la terza coordinata può provenire dal redius della terra, r = radice quadrata [x ^ 2 + y ^ 2 + z ^ 2] .

Quindi converti il ??tuo lat / long in x / y in metri. Avrai solo bisogno di un totale di 12756200m per coordinato (ecco i diametri della terra). Quindi il tuo valore totale dovrà essere compreso tra 0 e 25.512.400 (qualcun altro ha richiesto 40.000.000 perché utilizzavano long / lat) per avere una precisione di +/- 0,5 m.

Ciò comporterà solo 25 bit per posizione. Se fossi in te, farei solo precisione entro 2m e userei 24 bit per posizione, dato che sono 3 byte ordinati.

Inoltre, se si memorizzano le informazioni sul waypoint su un percorso, è possibile memorizzare ciascun waypoint come offset dall'ultimo waypoint. Come iniziare con un 24 bit x / y co-ord. E poi avere un 'aggiornamento' a 16 bit che regola la posizione aggiungendo / sottraendo metri x / y. 16 bit consentirebbe un aggiornamento del waypoint a più di 400 m di distanza. Quindi, se sai che il dispositivo non è pensato per gli aerei e gli aggiornamenti ogni tanto, anche questo potrebbe essere accettabile.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow