Algorithmusformat für codierte Polylinien

Die Polyliniencodierung ist ein mit Verlusten einhergehender Kompressionsalgorithmus, mit dem Sie mehrere Koordinaten als einzelne Zeichenfolge speichern können. Punktkoordinaten werden mit Werten mit Vorzeichen codiert. Wenn Sie nur einige wenige statische Punkte haben, können Sie auch das interaktive Hilfsprogramm für die Polyliniencodierung verwenden.

Beim Codierungsprozess wird ein Binärwert mithilfe des gängigen base64-Codierungsschemas in eine Reihe von ASCII-Zeichencodes umgewandelt: Um die korrekte Anzeige dieser Zeichen sicherzustellen, wird zu den codierten Werten der Wert 63 (ASCII-Zeichen „?“) addiert, bevor sie in ASCII konvertiert werden. Der Algorithmus prüft außerdem, ob zusätzliche Zeichencodes für einen gegebenen Punkt vorhanden sind, indem das niedrigstwertige Bit jeder Bytegruppe geprüft wird. Hat dieses Bit den Wert 1, ist der Punkt noch nicht vollständig definiert und es müssen weitere Daten folgen.

Um Platz zu sparen, enthalten die Punkte zudem nur den Offset vom vorherigen Punkt (natürlich mit Ausnahme des ersten Punkts). Alle Punkte sind als ganze Zahlen mit Vorzeichen in Base64 codiert, da es sich bei den Längengrad- und Breitengradangaben um Werte mit Vorzeichen handelt. Das Codierungsformat innerhalb einer Polylinie muss die beiden Koordinaten für die geografische Breite und Länge mit einer angemessenen Genauigkeit darstellen können. Angesichts eines maximalen Längengrads von +/- 180 Grad mit einer Genauigkeit von 5 Dezimalstellen (180,00000 bis -180,00000) ist ein binärer 32-Bit-Ganzzahlwert mit Vorzeichen erforderlich.

Beachten Sie, dass der umgekehrte Schrägstrich innerhalb von Zeichenfolgenliteralen als Escapezeichen interpretiert wird. In jeder Ausgabe dieses Hilfsprogramms müssen umgekehrte Schrägstriche innerhalb von Zeichenfolgenliteralen in doppelte umgekehrte Schrägstriche umgewandelt werden.

Die Schritte zur Codierung eines solchen Werts mit Vorzeichen sind nachfolgend beschrieben.

  1. Als Ausgangswert mit Vorzeichen soll der Wert
    -179,9832104 dienen.
  2. Multiplizieren Sie den Dezimalwert mit 1e5 und runden Sie das Ergebnis:
    -17998321
  3. Wandeln Sie den Dezimalwert in einen Binärwert um. Beachten Sie, dass ein negativer Wert mit seinem Zweierkomplement berechnet werden muss, indem der Binärwert invertiert und zum Ergebnis 1 addiert wird:
    00000001 00010010 10100001 11110001
    11111110 11101101 01011110 00001110
    11111110 11101101 01011110 00001111
  4. Verschieben Sie den Binärwert um ein Bit nach links:
    11111101 11011010 10111100 00011110
  5. Wenn der ursprüngliche Dezimalwert negativ ist, invertieren Sie diese Codierung:
    00000010 00100101 01000011 11100001
  6. Teilen Sie den Binärwert in 5-Bit-Blöcke auf (beginnen Sie auf der rechten Seite):
    00001 00010 01010 10000 11111 00001
  7. Kehren Sie die Reihenfolge der 5-Bit-Blöcke um:
    00001 11111 10000 01010 00010 00001
  8. ODERN Sie jeden Wert mit 0x20, wenn ein weiterer Bit-Block folgt:
    100001 111111 110000 101010 100010 000001
  9. Konvertieren Sie jeden Wert in einen Dezimalwert:
    33 63 48 42 34 1
  10. Addieren Sie zu jedem Wert 63:
    96 126 111 105 97 64
  11. Konvertieren Sie jeden Wert in den entsprechenden ASCII-Code:
    `~oia@

In der folgenden Tabelle sind einige Beispiele für codierte Punkte aufgeführt, wobei die Codierungen als Offsets von den vorherigen Punkten angegeben sind.

Beispiel

Punkte: (38,5, -120,2), (40,7, -120,95), (43,252, -126,453)



Breitengrad Längengrad Breitengrad in E5 Längengrad in E5 Änderung des Breitengrads Änderung des Längengrads Codierter Breitengrad Codierter Längengrad Codierter Punkt
38,5 -120,2 3850000 -12020000 +3850000 -12020000 _p~iF ~ps|U _p~iF~ps|U
40,7 -120,95 4070000 -12095000 +220000 -75000 _ulL nnqC _ulLnnqC
43,252 -126,453 4325200 -12645300 +255200 -550300 _mqN vxq`@ _mqNvxq`@

Codierte Polylinie: _p~iF~ps|U_ulLnnqC_mqNvxq`@

Feedback geben zu...

Google Maps APIs
Google Maps APIs