Format Algoritme Polyline yang Dienkodekan

Encoding polyline adalah algoritme kompresi lossy yang memungkinkan Anda menyimpan serangkaian koordinat sebagai string tunggal. Koordinat titik dienkodekan menggunakan nilai yang ditandatangani. Jika Anda hanya memiliki beberapa titik statis, sebaiknya gunakan utilitas encoding polyline interaktif.

Proses encoding mengonversi nilai biner menjadi serangkaian kode karakter untuk karakter ASCII menggunakan skema encoding base64 yang sudah dikenal: untuk memastikan tampilan karakter ini yang tepat, nilai yang dienkode dijumlahkan dengan 63 (karakter ASCII 'Snapshot#39;) sebelum mengonversinya ke ASCII. Algoritme ini juga memeriksa kode karakter tambahan untuk titik tertentu dengan memeriksa bit yang paling tidak signifikan dari setiap grup byte; jika bit ini ditetapkan ke 1, titik belum sepenuhnya terbentuk dan data tambahan harus mengikuti.

Selain itu, untuk menghemat ruang, titik hanya menyertakan offset dari titik sebelumnya (kecuali tentu saja untuk titik pertama). Semua titik dienkode dalam Base64 sebagai bilangan bulat yang ditandatangani, karena garis lintang dan bujur adalah nilai yang ditandatangani. Format encoding dalam polyline harus mewakili dua koordinat yang mewakili lintang dan bujur dengan presisi yang wajar. Mengingat garis bujur maksimum +/- 180 derajat dengan presisi 5 angka desimal (180.00000 hingga -180.00000), hal ini menghasilkan nilai bilangan bulat biner bertanda 32 bit.

Perhatikan bahwa garis miring terbalik ditafsirkan sebagai karakter escape dalam literal string. Setiap output utilitas ini harus mengonversi karakter garis miring kembali ke garis miring terbalik ganda dalam literal string.

Langkah-langkah untuk mengenkode nilai yang ditandatangani tersebut dijelaskan di bawah ini.

  1. Ambil nilai awal yang ditandatangani:
    -179.9832104
  2. Ambil nilai desimal dan kalikan dengan 1e5 dan bulatkan hasilnya:
    -17998321
  3. Konversikan nilai desimal menjadi biner. Perhatikan bahwa nilai negatif harus dihitung menggunakan kedua komplemennya dengan membalik nilai biner dan menambahkannya ke hasil:
    00000001 00010010 10100001 11110001
    11111110 11101101 0101010101010101010101010101010101010101010101010101 1010101010101010101010101010101010101011
  4. Geser nilai biner ke kiri sebanyak satu bit:
    11111101 11011010 10111100 00011110
  5. Jika nilai desimal asli negatif, balik enkode ini:
    00000010 00100101 01000011 11100001
  6. Bagi nilai biner menjadi potongan 5 bit (dimulai dari sisi kanan):
    00001 00010 01010 10000 11111 00001
  7. Tempatkan potongan 5 bit ke dalam urutan terbalik:
    00001 11111 10000 01010 00010 00001
  8. ATAU setiap nilai dengan 0x20 jika potongan bit lain mengikuti:
    100001 111111 110000 101010 100010 000001
  9. Konversikan setiap nilai ke desimal:
    33 63 48 42 34 1
  10. Tambahkan 63 ke setiap nilai:
    96 126 111 105 97 64
  11. Konversikan setiap nilai ke padanan ASCII-nya:
    `~oia@

Tabel di bawah menunjukkan beberapa contoh titik yang dienkode, yang menampilkan encoding sebagai serangkaian offset dari titik sebelumnya.

Contoh

Poin: (38.5, -120.2), (40.7, -120.95), (43.252, -126.453)

Lintang Bujur Garis Lintang dalam E5 Garis Bujur dalam E5 Perubahan dalam Garis Lintang Perubahan dalam Garis Bujur Garis Lintang yang Dienkodekan Garis Bujur yang Dienkodekan Titik yang Dienkodekan
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`@

Polyline yang dienkode: _p~iF~ps|U_ulLnnqC_mqNvxq`@