Latitudine/Longitudine di archiviazione e compressione in C

Qualcuno sa la più efficace rappresentazione lat/long coordinate? Livello di precisione dovrebbe essere sufficiente per i consumatori di dispositivi GPS.

La maggior parte delle implementazioni sembrano utilizzare double per ogni unità, ma io sospetto che un float o punto fisso formato dovrebbe essere sufficiente. Sarei curioso di sentire da chiunque abbia provato a comprimere e archiviare le matrici di grandi dimensioni di questi valori.

EDIT:

In altre parole, che cosa è la precisione minima necessaria per rappresentare lat/long per un consumatore a livello di dispositivo?

  • Cosa stai cercando di fare? Sei la memorizzazione di percorsi?
  • Memorizzare e trasmettere i dati GPS su dispositivi di elettronica di consumo.
InformationsquelleAutor Justicle | 2009-08-03



10 Replies
  1. 14

    Personalmente, io uso un 32 bit decimale di punto fisso di rappresentanza, dividendo 1.000.000 per Evan risposta e i miei commenti.

    Tuttavia, se lo spazio è veramente ad un premio, qui sono alcune idee aggiuntive:

    • Si potrebbe usare una 26 bit di punto fisso di rappresentanza sul filo. Questo richiederà di marshalling e unmarshalling la latitudine e la longitudine in un grande array di byte, ma vi farà risparmiare 12 bit, per ogni location, oltre il valore a 32 bit rappresentazione, quasi il 19% di risparmio, quindi potrebbe essere la pena.

    • Si potrebbe approfittare del fatto che i valori di longitudine bisogno di meno precisione come ci si avvicina ai poli – hanno solo bisogno di 26 bit pena all’equatore. Così si potrebbe scrivere un regime in cui il numero di bit utilizzati per codificare la longitudine dipende dal valore della latitudine.

    • Se i dati sono altre comprimibile di attributi di dire, che tutti i punti sono di solito abbastanza vicini tra loro – si potrebbe sfruttare al meglio quelle, come l’utilizzo di un delta schema di codifica (in cui ogni punto oltre il primo può essere codificato come un delta a partire dall’ultimo punto).

  2. 10

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

    Avete bisogno di un misuratore di precisione (3ft) per essere in grado di risolvere gps di precisione di un ordine di grandezza.

    Pertanto è necessario precisiton per memorizzare 40.000.000 di valori diversi. Che al minimo 26 bit di informazione. Una versione a 32 bit float o int farà bene.

    • Grazie per la rottura verso il basso.
    • No, non è necessario memorizzare 40,075,020 valori diversi per avere un metro di risoluzione, che richiede 26 bit.
    • In realtà, a 32 bit, IEEE mobile ha 23 esplicito bit di frazione (e, si presume 1) per 24 efficace bit di significante. Che è solo in grado di distinguere 16 milioni di valori unici, di 40 milioni di euro richiesti. Guardò in altro modo, è possibile rappresentare la posizione all’interno di 2,4 metri all’equatore, che può essere comunque abbastanza vicino.
    • Io magra verso un punto fisso, la rappresentazione in quanto i carri non hanno vantaggi per questo tipo di applicazione, e firmato un valore a 32 bit, ha un sacco di bit a disposizione per prendere una comoda scala.
    • Non dimenticate il segno, che ti dà un altro po’, dal momento che la rappresentazione predefinita è di ±180° di latitudine e longitudine. Poiché la precisione è meglio se si è vicino a zero a 32 bit carri dà 1m precisione ad eccezione di ca 1/5 del globo vicino alla linea del cambiamento di data.
    • Dipende dall’applicazione. WP suggerisce che “civile il fix del GPS sotto una chiara visione del cielo sono in media precisa di circa 5 metri”, ma con “appositamente attrezzata ricevitori” (ad esempio, geometri) “l’errore potrebbe essere come minimo di 2 millimetri”. Scegli la tua precisione, e rendersi conto che il prossimo anno $5 telefono cellulare sarà probabilmente in grado di batterlo. 🙂
    • nessun modo in inferno che sono civili dispositivi GPS preciso, in media, di 5 metri (in ogni caso, le precisioni sono solitamente misurata in senso statistico, con variazioni e deviazioni standard e così via – un numero non può riflettere la precisione). Quello che intendo è: una volta in un mentre il dispositivo misura la posizione nel raggio di 5 metri della vera posizione – un po ‘ come come un orologio rotto è giusta due volte al giorno.

  3. 9

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

    Vorrei usare un 32-bit di punto fisso di rappresentazione. Se i valori sono:

    42.915512,-99.521654 Vorrei memorizzare il values * 100000 in int32_t‘s (che può essere negativo).

    int32_t lat = 42915512;
    int32_t lon = -99521654;

    Questo è un buon compromesso tra il semplice e preciso (5 punti decimali è di solito abbastanza buono, si può sempre aumentare fino a 1000000 per ottenere 6 se necessario).

    Da visualizzare all’utente, fare ciò che caf suggerisce:

    … per visualizzare all’utente di utilizzare l’intero
    divisione e modulo, ad esempio, printf("Lat =
    %d.%06d\n", lat /1000000, abs(lat) %
    1000000)

    Questi saranno anche essere paragonabile/ordinabile in modo efficiente in quanto il relativo ordine verrà mantenuto.

    EDIT: un ulteriore vantaggio è che è possibile inviare in rete o memorizzati su disco in un formato binario, in modo portatile.

    • Forse essere un po ‘ più di attenzione a non cancellare il senso della differenza tra -77.521654 e 77.521654
    • Vorrei suggerire l’uso di un potere-di-due moltiplicatore piuttosto di 10.000. Utilizzando i 10.000 potrebbe essere leggibile se si scopre che si hanno per codificare i numeri, ma è abbastanza inutile altrimenti. Inoltre, se si utilizza questo metodo, utilizzare SEMPRE le macro/funzioni inline per la conversione ad/da double a int.
    • unsigned non è molto tritare dal momento che possono essere negativi. Inoltre, .0001 gradi può essere di ben 22 metri, e il consumatore GPS può essere più preciso di che. Quindi, utilizzare firmato int, e moltiplicare per almeno 1000000 (il valore massimo sarà ancora adattarsi facilmente in firma a 32 bit).
    • Grazie, buona punti, ho dimenticato di account per i valori negativi, ho modificato la mia risposta.
    • Oh, e non in ghisa a doppio e dividere per visualizzare all’utente di utilizzare l’intero dividere e modulo, ad esempio printf(“Lat = %d.%06d\n”, lat / 1000000, lat % 1000000)
    • un altro buon di cattura, risposta modificata per includere anche che.
    • Buon dio, basta usare un galleggiante. È più leggibile, per una cosa, se si memorizza i valori in un database.
    • In un altro post, commento, ha indicato che possono essere inviati attraverso la rete. In questo caso, un punto fisso di rappresentazione può essere più semplice nel lungo periodo.
    • Non usare istruzione printf! C operatore di modulo non è davvero un modulo, è un resto operatore, e dà risultati negativi per l’ingresso negativo. Per esempio, se lat=-1234567, il codice di stampa “-1.-234567”.
    • Ahh, punto molto bene. Gettare un abs() di tutto o laboratori() se è necessario utilizzare long (e regolare il specificatori di formato in modo appropriato).
    • C’è un errore di battitura? Dovrebbe 100000 (100,000) essere 1000000 (1,000,000)
    • Ho provato 2^24 e potrebbe non ottenere la parte decimale di tornare fuori lo stesso. Ad ESEMPIO 42.915512 era 42.15359742; utilizzo di 10^6 tuttavia ottenuto 42.915512. perl -E'$by=1_000_000; @c=(42.915512, -99.521654); say join ",", @c; sub to{ int($_[0]*$by)} sub fr{sprintf "%d.%d", int($_[0]/$by), abs($_[0])%$by} for(@c){ say(to($_)); say(fr(to($_))); }' opere durante la modifica di $by=(1<<24) non.
    • IMHO, non sottovalutare il valore di leggibile – né di mantenere un multiplo di 10. È un bel test di sanità mentale per vedere i valori che sono ancora in gradi (manca solo il punto decimale). E viaggi di andata e ritorno per/da un bel formato di visualizzazione con zero imprecisione – così non devi preoccuparti se ti ho incasinato di arrotondamento.

  4. 5

    Carri sarebbe più che sufficiente per la memorizzazione delle coordinate GPS, anche se di livello consumer dispositivi GPS era da nessuna parte vicino la precisione chiesto per loro. Se si non credo che questo sia vero, provare queste due semplici esperimenti:

    1. Prendere due o più dispositivi GPS in un punto su un campo da qualche parte, e annotare le coordinate misurate da ogni dispositivo. Andare all’indietro e tracciare i punti per ogni dispositivo su una mappa (penso che Google ha qualcosa che fa proprio questo). Sarete sorpresi presso la distanza tra i punti (anche se sono tutti dovrebbe essere la misurazione esatta stesso posto).
    2. Prendere il vostro (presumibilmente) più preciso dispositivo e metterlo da qualche parte dove si può ottenere la posizione del satellite, ma non piovere, e registrare una serie di misure prese per un paio di giorni. Trama di tutte le letture (come in #1). Di nuovo, sarete sorpresi da quanto i punti (che dovrebbe essere lo stesso o quasi lo stesso) vagare per tutta la mappa, a volte tanto quanto un paio di centinaia di metri.

    Ho scritto in applicazioni per GPS e Pda per anni, e ho verificato questo per dubbia clienti più e più volte (ho anche vinto le scommesse in questo modo). Ci sono di qualità superiore GPS dispositivi là fuori che ottenere la migliore precisione di questo, ma la migliore precisione si ottiene con le più costose chipset, e i dispositivi sono lasciati in uno spot per giorni o addirittura settimane, con le letture in media nel corso del tempo.

    Quattro byte float è molto più accurata rispetto ai dispositivi stessi. Sarebbe, naturalmente, non farti del male in tutto il, usare una doppia invece, come lungo come il 2X fattore non è un problema per voi.

    • Buon punto – credo che la domanda potrebbe essere riformulato come “che Cosa è il minimo precisione richiesta per il consumatore dispositivi gps?”
    • il diavolo downvoted tutte le risposte?! Personalmente penso che sia la tua e la mia sono state risposte valide.
    • Ho avuto persone che nel mondo reale sono particolarmente arrabbiato con me per pungere la precisione del GPS mito (e poi io prendere i loro soldi). E ho incontrato persone su StackOverflow che si sentono che a 32 bit carri appartengono alla stessa categoria dei tubi a vuoto. Quindi questa domanda è la tempesta perfetta, in un certo senso. 🙂
  5. 2

    23 bit di precisione a 179 gradi di longitudine dà al di sotto dei 10 metri di precisione, che è la migliore che i normali dispositivi GPS dare. 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

    Così IEEE 754 singola precisione numero a virgola mobile, nota per il compilatore C come float, wil essere appena sufficiente per la rappresentazione. Attenzione a usare galleggianti per esteso calcoli! Errore di arrotondamento può mangiare il vostro pranzo. Consultare un analista numerico.

  6. 2

    In Garmin IMG mappa di formato di archivio di coordinate all’interno di riquadri utilizzando galleggianti per impostare i bordi delle caselle. Coords all’interno del box sono definiti utilizzando un numero variabile di bit sono solo lineare tra i valori di min e max a seconda della precisione necessaria.

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

    Quindi un valore di:

    32768,32768 sarebbe convertito a 49,5, 122.5

    16384,0 sarebbe 49.25, 122.0

    Se avete bisogno di meno precisione, la stessa uscita potrebbe essere generato con un numero di bit=4

    8,8 sarebbe convertito a 49,5, 122.5

    4,0 sarebbe 49.25, 122.0

  7. 2

    Se la memorizzazione di matrici di grandi dimensioni di questi valori, ci sono alcuni semplici trucchi se si fa un delta di compressione, e negozio di deltas, è possibile ridurre notevolmente le dimensioni di un flusso di dati.
    Si può fare deltas da un “punto chiave”

    K D D D D D D D D D D K D D D D …

    k + d raggiungere qualsiasi punto d

    Il delta di riferimento precedente K, in modo da ricostruire in qualsiasi momento avete bisogno di un K e D

    o si può fare incrimental delta

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

    Questo può richiedere più somme a raggiungere la posizione desiderata. ma i dati sono ridotte. COSÌ reconsturct

    k+i+i+i per ottenere il punto 4

    Infine, è possibile combinare entrambi

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

    Questo è come mpeg-2 con IPB fotogrammi, ma in questo modo si sono mai più di 4 somme a qualsiasi posizione, e si ottiene alcuni dei benefici del Delta e Incrimental di Compressione.

  8. 1

    Puoi pack sia la latitudine e la longitudine valori in un singolo numero intero a 32 bit con una risoluzione peggiore ~2.4 metri/pixel (all’equatore) se si utilizza un ricorsiva sistema di rivestimento. L’utilizzo di due bit per ogni livello, è possibile memorizzare fino a 16 livelli di 32 bit. Si può avere un’idea di come vorresti lavorare in questo articolo su Virtual Earth del sistema di rivestimento. Questo utilizza Mercator, quindi non dovrebbe dare problemi per i polacchi. Si potrebbe utilizzare invece una proiezione diversa e ancora ottenere risultati molto simili.

    Questo può anche essere utilizzato per un ruvida filtro per trovare tutti i punti all’interno di un determinato tegola padre dal momento che i primi N bit sarà la stessa (e quindi la ricerca diventa maschera di bit).

    • -1: Mele e arance: Guardando la tabella nell’articolo, al livello 16, che ci dà una risoluzione di 2,4 metri/px, la mappa è 16.777.216 pixel di larghezza (2^24), così al livello di zoom 16, abbiamo bisogno di 24 bit per memorizzare ogni lat/long valore, cioè 48 bit per memorizzare entrambi.
  9. 1

    Supponendo che la terra sia una sfera perfetta (non è, ma abbastanza vicino) con raggio ‘R’ di 3959 miglia (o ×5280 ft/mi = 20903520 ft), la circonferenza è 131340690 piedi (con l’utilizzo di 2×PI×R).

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

    Se si desidera memorizzare lat/giù per una precisione di 3 metri, è necessario essere in grado di memorizzare 43780230 (131340690/3) longitudine valore e 21890115 (65670345/3) i valori della latitudine. 43780230 richiede 25.38 bit (log(43780230)/log(2)) per memorizzare e 21890115 richiede 24.38 bit (log(21890115)/log(2)) per memorizzare o appena al di sotto del 50 bit (o 6.25 byte).

    Quindi la domanda diventa, se si desidera memorizzare le coordinate di latitudine e longitudine in soli 6 byte, quale sarà la precisione? Bene, 6 byte è di 48 bit. Che significa 23.5 bit per la latitudine e il 24,5 bit per la longitudine (longitudine ha il doppio dei valori, che è solo un po ‘ e 24.5-23.5=1 bit). Così 23.5 bit consente di rappresentare un numero da 0 a 11863282 (11863283 valori). E 65670345 piedi divisi da 11863283 valori è 5.53 piedi (e lo stesso valore di precisione, per la longitudine).

    LA LINEA di FONDO: Così, se si può vivere con i piedi 5.5 di precisione per entrambi latitudine e longitudine, puoi pack entrambi i valori in soli sei byte.

    *NOTA A margine: per quanto Riguarda i commenti che la latitudine e la longitudine sono orribili per memorizzare le informazioni posizionali attorno a una sfera (perché c’è meno informazioni a negozio al poli) – beh, i commenti non tenere premuto fino a che la matematica! Proviamo a capire. Supponiamo di voler progettare un nuovo sistema perfetto, in grado di registrare e mettere un palo nel terreno al centro di ogni piede quadrato di terra. La superficie della terra (con una R di 3959 miglia; la formula per l’area della superficie di una sfera) è 5490965469267303 SQ FT – che molti pali richiede 52.29 bit per rappresentare. Ora esistente latitudine e longitudine sistema utilizza una forma rettangolare di sistema. La larghezza del rettangolo è la circonferenza della terra e l’altezza del rettangolo è di 1/2 di circonferenza) – che è 131340690 * 65670345 (vedere sopra), o 8625188424838050 SQ FT – che richiede 52.94 bit per rappresentare (sistema di luoghi “di troppo” pali nel terreno intorno ai poli). Così, la sconvolgente risposta è che sia il nuovo sistema perfetto, e il vecchio lat/lng sistema, sarebbero ENTRAMBE richiedono 53 effettivo di bit per memorizzare un unico luogo sulla terra, fino a 1 piede precisione!

  10. 0

    Io sono sorpreso che nessuno ha postato il fatto che long/lat è un modo terribile per memorizzare i dati su una sfera (qualcuno ha menzionato longitudine richiede meno precisione vicino ai poli).

    Fondamentalmente è possibile memorizzare i dati di posizione X e Y co-parole in metri. Immaginate un cubo attorno alla terra che exactally adatta (haha ok quasi si adatta). Hai solo bisogno di memorizzare la posizione X e Y, non tutte e 3 le co-parole, perché il 3-rd co-ord può venire dalla redius della terra, r = radice quadrata[x^2 + y^2 + z^2].

    Così convertire le coordinate lat/long per x/y in metri. Avrete bisogno solo di un totale di 12756200m per co-ord (è il diametro della terra). Quindi, il valore totale solo span 0 a 25,512,400 (qualcuno sosteneva di 40.000.000 perché stavano utilizzando long/lat) per una precisione di +/- 0,5 m.

    Che si tradurrà in soli 25 bit per posizione. Se fossi in te, vorrei solo fare una precisione di un raggio di 2 m e 24 bit per la posizione, che è un ordine di 3 byte.

    Anche se si memorizzano modo-punto di informazione su di un percorso, è possibile memorizzare ogni modo-punto come un offset dall’ultimo waypoint. Come iniziare con una risoluzione di 24 bit x/y co-ord. E poi hanno un 16bit “aggiornamento” che consente di regolare la posizione aggiungendo/sottraendo x/y metri. 16bit, per consentire a un waypoint di aggiornamento per essere più di 400m di distanza. Quindi, se il dispositivo non è pensato per gli aerei e gli aggiornamenti ogni tanto, questo potrebbe essere accettabile anche.

    • Memorizzare le coordinate X/Y per una sfera non funziona. A tutti. Si perde un sacco di precisione vicino la sfera dell’intersezione con il piano XY, e non è possibile ricostruire la coordinata Z — si ottiene solo una metà di una sfera. Se siete alla ricerca per l’uniformità, l’uso tridimensionale a coordinate cartesiane. In caso contrario, lat/long è un buon modo di immagazzinare.
    • Wow, si dovrebbe dare un Garmin chiamare e spiegare loro come “terribile” di latitudine e longitudine sono per le informazioni sulla posizione. Che cosa stavano pensando tutti questi anni?
    • UTM utilizza un approccio simile con sua Latitudine e Longitudine coppie di coordinate X/Y “coordinate” fare il lavoro per le sfere. È tutta una questione di proiezione.
    • myforwik: il tuo approccio ha ancora problemi, però. Come Dietrich menziona, la versione di X/Y non è una buona proiezione. Hai bisogno di appiattire su un piano 2D, non un cubo 3D.
    • Programmazione Perle (2a Edizione) (ACM Press) (Paperback) è un ottimo libro in cui si discute la conversione di x,y,z per ridurre il numero di costose operazioni trigonometriche che si è verificato per una particolare applicazione dei dati della mappa.
    • La terra non è una sfera è un geoide. Il suo raggio è diverso in luoghi diversi. Hai bisogno di x,y,z per sapere i r a che punto. Pertanto non è possibile dedurre z conoscendo solo x e y.
    • Penso che la maggior parte di noi sa che la Terra non è una sfera perfetta. Ho solo Dietrich formulazione. Inoltre, solo perché la Terra non è una sfera non significa che non può essere approssimata da una sfera.
    • In realtà ho cominciato non solo a ‘inventare’. Il mio gps memorizza i dati in questo modo. Ha un look up table per un raggio di rom. Qualsiasi errore nel raggio è solo andare a essere un fattore molto piccolo comunque. Funziona dove siete nel mondo, semplicemente chiedere all’utente cosa countery/regione in cui sono, o dove il sole è nel cielo.

Lascia un commento