Latitude/Longitude-Speicherung und Komprimierung in C

https://stackoverflow.com/questions/1220377

10-07-2019
|

Frage

Kennt jemand die effizienteste Darstellung für Breiten- und Längenkoordinaten?Die Genauigkeit sollte für Consumer-GPS-Geräte ausreichend sein.

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

BEARBEITEN:

Mit anderen Worten: Wie hoch ist die Mindestgenauigkeit, die für die Darstellung von Breiten- und Längengraden bei einem Verbrauchergerät erforderlich ist?

Lösung

Ich persönlich würde eine 32-Bit dezimal Festpunktdarstellung verwenden, von 1.000.000 pro Evan Antwort zu teilen und meine Kommentare.

Wenn jedoch Raum wirklich an erster Stelle steht, sind hier einige zusätzliche Ideen:

Sie können eine 26-Bit-Festkomma-Darstellung auf dem Draht verwenden. Dies erfordert Rangier- und unmarshalling die geografische Breite und Länge in eine große Reihe von Bytes, aber Sie werden 12 Bits für jeden Ort auf der 32-Bit-Wert Darstellung speichern -. Fast 19% Einsparung, so könnte es auch sinnvoll sein,
Sie sich die Tatsache zunutze nehmen könnte, dass Längenwerte weniger Präzision benötigen, wie Sie zu den Polen näher zu kommen - sie brauchen nur 26 Bits am Äquator wert. So könnte man ein System schreiben, wo die Anzahl von Bits verwendet, um die Länge zu codieren, auf dem Wert der Breite abhängig ist.
Wenn Ihre Daten anderen komprimierbaren Attribute hat - sagen wir, alle Punkte sind in der Regel ziemlich nahe beieinander - Sie spezifischen Vorteil derer nehmen könnte, wie ein Delta-Codierungsschema verwendet (wobei jeder Punkt außer dem ersten können codiert werden als Delta vom letzten Punkt).

Andere Tipps

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

Sie benötigen einen Meter Genauigkeit (3 ft) in der Lage zu sein, aus-lösen GPS-Genauigkeit durch eine Größenordnung.

Sie benötigen daher precisiton 40.000.000 verschiedene Werte zu speichern. Das ist bei mindestens 26 Bits an Informationen. Ein 32-Bit float oder int wird gut tun.

EDIT:. ein paar Punkte aus den Kommentaren hinzugefügt, 32-Bit-Werte sollten anzubieten genug Präzision der Lage sein,

würde ich eine 32-Bit-Festkomma-Darstellung verwenden. Wenn die Werte sind:

42.915512, -99.521654 Ich würde speichern die values * 100000 in int32_t des (sie kann negativ sein).

int32_t lat = 42915512;
int32_t lon = -99521654;

Dies ist ein guter Kompromiss zwischen einfachen und genauen ( 5 Dezimalpunkten ist in der Regel gut genug, könnte man immer es bump up 1000000 6 zu erhalten, wenn erforderlich).

für den Benutzer anzuzeigen, tun, was caf schlägt vor:

... für die Benutzer angezeigt werden - verwenden integer divide und Modulo, zB printf("Lat = %d.%06d\n", lat / 1000000, abs(lat) % 1000000)

Diese werden auch auf eine effiziente Art und Weise vergleichbar / sortierbar sein, da die relative Reihenfolge beibehalten wird.

EDIT:. ein zusätzlicher Vorteil ist, dass es über ein Netzwerk oder gespeichert auf der Festplatte in einem Binärformat in einem tragbaren Weise gesendet werden,

Floats wäre viel mehr als ausreichend GPS-Koordinaten für die Speicherung, auch wenn Verbraucher-Level-GPS-Geräte hatten irgendwo in der Nähe der Genauigkeit für sie beansprucht wird. Wenn Sie nicht glauben dies wahr ist, versuchen diese beiden einfachen Experimenten:

Nehmen Sie zwei oder mehr GPS-Geräten aus zu einem Punkt auf einem Feld irgendwo, und notiere die Koordinaten von jedem Gerät gemessen nach unten. Gehen Sie zurück nach innen und zeichnen Sie die Punkte von jedem Gerät auf einer Karte (ich denke, Google hat etwas, das dies für Sie tut). Sie werden die Punkte an, wie weit voneinander entfernt überrascht sein (obwohl sie alle genau die gleiche Stelle zu messen soll).
Nehmen Sie sich (angeblich) genaueste Gerät, und legen Sie es irgendwo, wo es einen Satelliten-Fix bekommen, aber nicht beregnet wird erhalten, und eine Reihe von Messungen über ein paar Tage gedauert aufzunehmen. Plot alle Messwerte (wie in # 1). Auch hier werden Sie überrascht, wie die Punkte (die alle die gleiche oder annähernd die gleiche sein sollte) wandern über die ganze Karte, manchmal so viel wie ein paar hundert Meter.

Ich habe Anwendungen für GPS-fähigen PDAs seit Jahren zu schreiben, und ich habe dies für dubiose Kunden über prüfe und immer wieder (ich habe sogar Wetten auf diese Weise gewonnen). Es gibt hochwertigere GPS-Geräte gibt, die als diese eine bessere Genauigkeit zu tun erreichen, aber die bessere Genauigkeit ist mit teureren Chipsätze erreicht, und die Geräte sind für Tage an einer Stelle nach links oder sogar Wochen, wobei die Messwerte über die Zeit gemittelt.

Ein Vier-Byte-float ist viel genauer als die Geräte selbst . Es wäre natürlich nicht verletzen alle eine doppelte stattdessen zu verwenden, solange der 2X Faktor für Sie kein Problem.

23 Bit Genauigkeit bei 179 Längengrade gibt unter 10-Meter-Genauigkeit, welche die beste ist, die gewöhnliche GPS-Geräte geben. 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

So ein IEEE 754 mit einfacher Genauigkeit Gleitkommazahl, zu Ihren C-Compiler als float bekannt, wil zur Darstellung nur ausreichend sein. Hüten Sie sich vor Schwimmer für erweiterte Berechnungen verwenden! Rundungsfehler kann essen Sie Ihr Mittagessen. Konsultieren Sie einen numerischen Analyst.

In Garmins IMG Kartenformat speichern sie Koordinaten innerhalb Begrenzungskästen Schwimmer mit den Kanten der Boxen zu setzen. Coords innerhalb der Felder definiert eine variable Anzahl von Bits verwenden, sind nur zwischen minimalen und maximalen Werten linear auf die Genauigkeit je benötigt.
Zum Beispiel: minlat = 49,0, MAXLAT = 50,0, Minlon = 122,0, maxlon = 123,0, die Anzahl der Bits = 16

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

Wenn Sie weniger Präzision benötigen, könnte die gleiche Leistung mit einer Anzahl von Bits = 4
erzeugt werden 8,8 würde auf 49,5, 122,5
umgewandelt werden 4,0 wäre 49,25, 122,0

Wenn Sie große Arrays dieser Werte speichern, gibt es ein paar einfache Tricks, wenn Sie eine Delta-Kompression zu tun, und speichern Deltas, können Sie erheblich die Größe eines Datenstroms reduzieren. Sie können Deltas von einem „Kernpunkt“ do

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

k + d Sie zu jedem d Punkt

Die Deltas verweisen alle vorherigen K, so dass jeder Punkt zu rekonstruieren, müssen Sie eine K und D

oder Sie können incrimental Deltas tun

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

Dies kann mehrere Summen, um die gewünschte Position zu bekommen. aber die Daten sind insgesamt kleiner. SO reconsturct

k + i + i + i zum 4. Punkt zu gelangen

Schließlich können Sie beides kombinieren

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

Das ist wie MPEG-2 mit IPB Frames, aber diese Weise nie mehr als 4 Summen in eine beliebige Position sind, und Sie einige der Vorteile von Delta und Incrimental Kompression bekommen.

Sie können packen sowohl die Breite und Länge Werte in einem einzelnen 32-Bit-Integer mit einer Auflösung von im schlimmsten Fall ~ 2,4 Meter / Pixel (am Äquator), wenn Sie verwenden eine rekursive Kachelsystem. Unter Verwendung von zwei Bits pro Ebene können Sie 16 Levels speichern in 32 Bit. Sie können eine Vorstellung davon bekommen, wie das in diesem Artikel suchen funktionieren würde über Virtual Earth die Fliesen System . Dies nutzt Mercator, so wäre es Probleme für die Polen geben. Sie könnten stattdessen eine andere Projektion verwenden und immer noch sehr ähnliche Ergebnisse erhalten.

Dies kann auch für einen Grobfilter verwendet wird alle Punkte innerhalb einer bestimmten übergeordneten Kachel zu finden, da die ersten N Bits gleich sein wird (und so wird Suchen Bit Maskierung).

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

360 Längengrade umfassen 131340690 Fuß.Der 180. Breitengrad umfasst 65670345 Fuß.

Wenn Sie Lat/Lng mit einer Genauigkeit von 3 Fuß speichern möchten, müssen Sie in der Lage sein, 43780230 (131340690/3) Längengrade und 21890115 (65670345/3) Breitengrade zu speichern.43780230 erfordert 25,38 Bit (log(43780230)/log(2)) zum Speichern und 21890115 erfordert 24,38 Bit (log(21890115)/log(2)) zum Speichern – also knapp 50 Bit (oder 6,25 Byte).

Die offensichtliche Frage lautet also: Wie hoch wird die Genauigkeit sein, wenn Sie Breiten- und Längengrade in nur 6 Bytes speichern möchten?Nun, 6 Bytes 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 ergibt 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 den Breiten- und Längengrad leben können, können Sie beide Werte in nur sechs Bytes packen.

*Eine Randbemerkung:Zu den Kommentaren, dass Breiten- und Längengrade für die Speicherung der Positionsinformationen rund um eine Kugel schrecklich sind (weil an den Polen weniger Informationen gespeichert werden müssen) – nun, diese Kommentare halten der Mathematik nicht stand!Lass es uns herausfinden.Nehmen wir an, wir möchten ein neues perfektes System entwerfen, das in der Mitte jedes Quadratfußes der Erde einen Pfahl erfassen und im Boden platzieren kann.Die Erdoberfläche (mit einem R von 3959 Meilen;Formel für die Oberfläche einer Kugel) beträgt 5490965469267303 Quadratfuß – für die Darstellung dieser vielen Einsätze sind 52,29 Bit erforderlich.Jetzt verwendet das bestehende Breiten- und Längengradsystem ein rechteckiges System.Die Breite des Rechtecks ist der Umfang der Erde und die Höhe des Rechtecks beträgt die Hälfte des Umfangs) – also 131340690 * 65670345 (siehe oben) oder 8625188424838050 SQ FT –, was 52,94 Bit zur Darstellung erfordert (dieses System platziert). „zu viele“ Pfähle im Boden rund um die Pfähle).Die schockierende Antwort lautet 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 einzelnen Standort auf der Erde zu speichern, und zwar bis zu einer Genauigkeit von 1 Fuß!

Ich bin überrascht, dass niemand die Tatsache geschrieben hat, dass long / lat eine schreckliche Art und Weise ist eine Kugel zum Speichern von Daten auf (jemand erwähnt hat, dass Länge erfordert weniger Präzision in der Nähe des Pols).

Grundsätzlich können Sie Daten speichern Position als X und Y Co-ords in Metern. Stellen Sie sich einen Würfel um die Erde, die exactally Passungen (haha ok fast passt es). Sie müssen nur Speicher X und Y-Position, nicht alle 3 co-ords, weil die 3-rd co-ord vom redius der Erde kommen, r = Quadratwurzel [x ^ 2 + y ^ 2 + z ^ 2] .

So wandeln Sie Ihre lat / long x / y in Metern. Sie werden nur insgesamt 12756200m pro Co-ord müssen (das ist der Durchmesser der Erde). So Ihr Gesamtwert wird nur 0 bis 25.512.400 zu überbrücken hat (jemand anderes 40.000.000 beansprucht, weil sie lange wurden mit / lat), um genau 0,5 m bis +/-.

Das wird in nur 25 Bits pro Position zur Folge hat. Wenn ich Sie wäre, würde ich Genauigkeit nur innerhalb 2m und verwenden 24 Bit pro Position, als dass ein ordentlich 3 Bytes ist.

Auch wenn Sie auf einem Pfad Wegpunktinformationen speichern, können Sie jeden Wegpunkt speichern, wie ein aus dem letzten Wegpunkt versetzt. Wie beginnen mit einer 24-Bit-x / y Co-ord. Und dann haben ein 16bit ‚update‘, der die Position passt durch das Hinzufügen / Subtrahier x / y Meter. 16bit wäre ein Wegpunkt Update ermöglicht über 400 m entfernt zu sein. Also, wenn Sie das Gerät einfach nicht für Flugzeuge und Updates oft jeder so gemeint ist, könnte dies auch akzeptabel sein.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow