Speicherung und Komprimierung von Breiten-/Längengraden in C

Kennt jemand die effizienteste Darstellung für Lat/Long-Koordinaten? Das Genauigkeitsniveau sollte für Verbraucher-GPS-Geräte ausreichen.

Die meisten Implementierungen scheinen zu verwenden double für jede Einheit, aber ich bin misstrauisch, dass a float oder Festkommaformat sollte ausreichen. Ich wäre neugierig, von jemandem zu hören, der versucht hat, große Arrays dieser Werte zu komprimieren und / oder zu speichern.

BEARBEITEN:

Mit anderen Worten, was ist die Mindestgenauigkeit, die erforderlich ist, um Breiten-/Längengrad für ein Gerät auf Verbraucherebene darzustellen?

Persönlich würde ich eine 32-Bit-Dezimal-Festkommadarstellung verwenden und gemäß Evans Antwort und meinen Kommentaren durch 1.000.000 dividieren.

Wenn der Platz jedoch wirklich knapp ist, hier sind einige zusätzliche Ideen:

• Sie könnten eine 26-Bit-Festkommadarstellung auf dem Draht verwenden. Dies erfordert das Marshalling und Unmarshalling der Breiten- und Längengrade in ein großes Array von Bytes, spart Ihnen jedoch 12 Bit für jede Position gegenüber der 32-Bit-Wertdarstellung – fast eine Einsparung von 19 %, also könnte es sich durchaus lohnen.

• Sie könnten die Tatsache ausnutzen, dass Längenwerte weniger genau sind, wenn Sie sich den Polen nähern – am Äquator benötigen sie nur 26 Bit. Sie könnten also ein Schema schreiben, bei dem die Anzahl der Bits, die zum Codieren des Längengrads verwendet werden, vom Wert des Breitengrads abhängt.

• Wenn Ihre Daten andere komprimierbare Attribute haben – sagen wir, alle Punkte liegen normalerweise ziemlich nahe beieinander -, können Sie diese gezielt nutzen, z. B. die Verwendung eines Delta-Codierungsschemas (bei dem jeder andere Punkt als der erste als Delta vom letzten codiert werden kann Punkt).

BEARBEITEN: Einige Punkte aus Kommentaren hinzugefügt, 32-Bit-Werte sollten in der Lage sein, genügend Präzision zu bieten.

Ich würde eine 32-Bit-Festkommadarstellung verwenden. Wenn die Werte sind:

42.915512,-99.521654 Ich würde die speichern values * 100000 in int32_t‘s (Sie können negativ sein).

int32_t lat = 42915512;
int32_t lon = -99521654;

Dies ist ein guter Kompromiss zwischen einfach und genau (5 Dezimalstellen sind normalerweise gut genug, Sie können es immer noch erhöhen 1000000 bekommen 6 wenn benötigt).

Um dem Benutzer anzuzeigen, tun Sie, was caf vorschlägt:

… um es dem Benutzer anzuzeigen – verwenden Sie ganzzahlige Division und Modulo, z printf("Lat =
%d.%06d\n", lat / 1000000, abs(lat) %
1000000)

Diese sind auch auf effiziente Weise vergleichbar/sortierbar, da die relative Reihenfolge beibehalten wird.

BEARBEITEN: Ein zusätzlicher Vorteil besteht darin, dass es über ein Netzwerk gesendet oder in einem binären Format portabel auf der Festplatte gespeichert werden kann.

Der Umfang der Erde beträgt ca. 40.000 km oder 24900 Meilen.

Sie benötigen eine Genauigkeit von einem Meter (3 Fuß), um die GPS-Präzision um eine Größenordnung übertreffen zu können.

Daher braucht man Präzision, um 40.000.000 verschiedene Werte zu speichern. Das sind mindestens 26 Informationsbits. Ein 32-Bit-Float oder Int ist gut geeignet.

Schwimmer wären mehr als ausreichend, um GPS-Koordinaten zu speichern, selbst wenn GPS-Geräte auf Verbraucherebene annähernd die für sie beanspruchte Genauigkeit hätten. Wenn Sie nicht glauben, dass dies wahr ist, versuchen Sie diese zwei einfachen Experimente:

1. Nehmen Sie zwei oder mehr GPS-Geräte mit an eine Stelle auf einem Feld und notieren Sie die von jedem Gerät gemessenen Koordinaten. Gehen Sie zurück und zeichnen Sie die Punkte von jedem Gerät auf einer Karte auf (ich denke, Google hat etwas, das dies für Sie erledigt). Sie werden überrascht sein, wie weit die Punkte voneinander entfernt sind (obwohl sie alle genau dieselbe Stelle messen sollen).
2. Nehmen Sie Ihr (angeblich) genauestes Gerät und platzieren Sie es an einem Ort, an dem es eine Satellitenfixierung erhalten kann, aber nicht darauf regnet, und zeichnen Sie eine Reihe von Messungen auf, die über ein paar Tage durchgeführt wurden. Zeichnen Sie alle Messwerte (wie in Nr. 1). Auch hier werden Sie überrascht sein, wie die Punkte (die alle gleich oder fast gleich sein sollten) über die ganze Karte wandern, manchmal um bis zu ein paar hundert Fuß.

Ich schreibe seit Jahren Anwendungen für GPS-fähige PDAs und habe dies immer wieder für dubiose Kunden verifiziert (ich habe auf diese Weise sogar Wetten gewonnen). Es gibt höherwertige GPS-Geräte, die eine bessere Genauigkeit erreichen, aber die bessere Genauigkeit wird mit teureren Chipsätzen erreicht, und die Geräte werden tage- oder sogar wochenlang an einem Ort belassen, wobei die Messwerte über die Zeit gemittelt werden.

Ein 4-Byte-Float ist viel genauer als die Geräte selbst. Es würde Ihnen natürlich überhaupt nicht schaden, stattdessen ein Double zu verwenden, solange der 2X-Faktor für Sie kein Problem darstellt.

Unter der Annahme, dass die Erde eine perfekte Kugel ist (sie ist es nicht, aber nahe genug) mit einem Radius „R“ von 3959 Meilen (oder ×5280 Fuß/Meile = 20903520 Fuß), beträgt der Umfang 131340690 Fuß (unter Verwendung von 2 × PI × R). .

360 Längengrade umfassen 131340690 Fuß. 180 Breitengrade umfassen 65670345 Fuß.

Wenn Sie Lat/Lng mit einer Genauigkeit von 3 Fuß speichern möchten, müssen Sie 43780230 (131340690/3) Längengradwerte und 21890115 (65670345/3) Breitengradwerte speichern können. 43780230 erfordert 25,38 Bit (log(43780230)/log(2)) zum Speichern und 21890115 erfordert 24,38 Bit (log(21890115)/log(2)) zum Speichern – oder knapp 50 Bit (oder 6,25 Byte).

Die offensichtliche Frage lautet also: Wenn Sie Längen- und Breitengrad in nur 6 Byte speichern möchten, wie hoch ist die Genauigkeit? Nun, 6 Byte sind 48 Bit. Das bedeutet 23,5 Bit für den Breitengrad und 24,5 Bit für den Längengrad (der Längengrad hat doppelt so viele Werte, also nur ein Bit und 24,5-23,5 = 1 Bit). Mit 23,5 Bit können Sie also eine Zahl von 0 bis 11863282 (11863283 Werte) darstellen. Und 65670345 Fuß geteilt durch 11863283 Werte sind 5,53 Fuß (und der gleiche Genauigkeitswert für den Längengrad).

DAS FAZIT: Wenn Sie also mit einer Genauigkeit von 5,5 Fuß für Breiten- und Längengrad leben können, können Sie beide Werte in nur sechs Bytes packen.

* EINE SEITLICHE ANMERKUNG: In Bezug auf Kommentare, dass Breiten- und Längengrade für das Speichern der Positionsinformationen um eine Kugel herum schrecklich sind (weil an den Polen weniger Informationen zu speichern sind) – nun, diese Kommentare halten der Mathematik nicht stand! Finden wir es heraus. Nehmen wir an, wir wollen ein neues, perfektes System entwerfen, das einen Pfahl im Boden im Zentrum jedes Quadratfußes der Erde aufzeichnen und platzieren kann. Die Oberfläche der Erde (mit einem R von 3959 Meilen; Formel für die Oberfläche einer Kugel) ist 5490965469267303 Quadratfuß – so viele Einsätze erfordern 52,29 Bits, um sie darzustellen. Jetzt verwendet das vorhandene Breiten- und Längengradsystem ein rechteckiges System. Die Breite des Rechtecks ​​ist der Umfang der Erde und die Höhe des Rechtecks ​​ist 1/2 des Umfangs) – das ist 131340690 * 65670345 (siehe ganz oben) oder 8625188424838050 SQ FT – was 52,94 Bits zur Darstellung erfordert (dieses System stellt ‘zu viele’ Pfähle im Boden um die Stangen herum). Die schockierende Antwort ist also, dass sowohl das neue perfekte System als auch das alte Lat/Lng-System BEIDE 53 tatsächliche Bits benötigen würden, um einen einzigen Ort auf der Erde mit einer Genauigkeit von bis zu 1 Fuß zu speichern!

23 Bit Genauigkeit bei 179 Längengraden ergeben eine Genauigkeit von weniger als 10 Metern, was das Beste ist, was gewöhnliche GPS-Geräte bieten. Am Äquator:

% 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

Also eine IEEE 754-Gleitkommazahl mit einfacher Genauigkeit, die Ihrem C-Compiler bekannt ist als float, wird zur Repräsentation gerade noch ausreichen. Hüten Sie sich vor der Verwendung von Gleitkommazahlen für erweiterte Berechnungen! Rundungsfehler können Ihr Mittagessen verzehren. Wenden Sie sich an einen numerischen Analysten.

Im IMG-Kartenformat von Garmin speichern sie Koordinaten in Begrenzungsrahmen, indem sie Floats verwenden, um die Ränder der Rahmen festzulegen. Koordinaten innerhalb der Boxen werden unter Verwendung einer variablen Anzahl von Bits definiert, die je nach benötigter Genauigkeit einfach linear zwischen minimalen und maximalen Werten liegen.

Zum Beispiel: minlat = 49,0, maxlat = 50,0, minlon = 122,0, maxlon = 123,0, Anzahl der Bits = 16

Also ein Wert von:
32768,32768 würde in 49,5, 122,5 umgewandelt werden
16384,0 wäre 49,25, 122,0

Wenn Sie weniger Genauigkeit benötigen, könnte die gleiche Ausgabe mit einer Anzahl von Bits = 4 generiert werden
8,8 würde umgewandelt in 49,5, 122,5
4,0 wäre 49,25, 122,0