-
Notifications
You must be signed in to change notification settings - Fork 4
/
831.txt
109 lines (75 loc) · 4.59 KB
/
831.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
[8] [DFN[Encoded Polyline]] は、一連の[[経緯度]]の組の[[リスト]]を単一の
[[ASCII文字列]]として[[符号化]]する方式です。
[[Google Maps]] で用いられています。
[REFS[
- [1] [CITE@en[Encoded Polyline Algorithm Format | Google Maps APIs | Google Developers]]
([TIME[2016-02-16 08:30:05 +09:00]] 版)
<https://developers.google.com/maps/documentation/utilities/polylinealgorithm>
]REFS]
* 符号化
[11] 一連の[[経緯度]]を[[符号化]]してそのままの順序で並べます。
[12] 各[[経緯度]]は、[[緯度]]、[[経度]]の順に[[符号化]]して順に並べます。
[13] 各値の最終文字は、 [N[0x3F]]-[N[0x5E]] を使って表されます。
それよりも前の文字は、[N[0x5F]]-[N[0x7E]] を使って表されます。
[10] 同じような性質を持つ他のデータにも適用できます。 [[Google]] 自身が
「level」の符号化に用いる例を示しています [SRC[>>4]]。
ただし、この場合[[経緯度]]のように値2つの組ではなく、値1つだけの[[リスト]]となります。
しかも、[[経緯度]]のように前の値との[[差]]を取ったり、[[ビット演算]]したりせずに、
5ビット[[符号無し整数]]としてそのまま符号化しているようです。
[19]
一般化すると、符号化器・復号器は次の引数を取る[[アルゴリズム]]となります。
[FIG(list members)[
: [F[組の個数]] : 1組のデータとして扱われるべき値の個数。[[緯度経度]]の場合は [N[2]]。
: [F[桁移動]] : 個々の値を[[整数]]化するため符号化時に掛け、復号時に割るべき数。
[[緯度経度]]の場合は 1e5。
: [F[差分]] : 1つ前の値との[[差]]かどうか。[[緯度経度]]の場合は[[真]]。
]FIG]
* 文脈
[9] [[Google Maps]] の [[API]] で[[符号化]]と[[復号]]の機能が提供されています。
[15] [[Strava]] の [[API]] で採用されています [SRC[>>14]]。
[REFS[
- [3] [CITE@en[Google Maps JavaScript API V3 Reference | Google Maps JavaScript API | Google Developers]] ([TIME[2016-09-27 13:07:08 +09:00]] 版) <https://developers.google.com/maps/documentation/javascript/reference?csw=1#encoding>
]REFS]
* メモ
[2] [CITE@en[mapbox/polyline: polyline encoding and decoding in javascript]]
([TIME[2016-04-20 15:07:00 +09:00]] 版)
<https://github.com/mapbox/polyline>
[4] [CITE@en[Interactive Polyline Encoder Utility | Google Maps APIs | Google Developers]]
([TIME[2016-02-16 08:30:08 +09:00]] 版)
<https://developers.google.com/maps/documentation/utilities/polylineutility>
[FIG(quote)[
[FIGCAPTION[
[5] [CITE@en[Encoded Polyline Algorithm Format | Google Maps APIs | Google Developers]]
([TIME[2016-07-13 06:14:37 +09:00]])
<https://developers.google.com/maps/documentation/utilities/polylinealgorithm>
]FIGCAPTION]
> Polyline encoding is a lossy compression algorithm that allows you to store a series of coordinates as a single string. Point coordinates are encoded using signed values.
]FIG]
[FIG(quote)[
[FIGCAPTION[
[6] [CITE@en[Interactive Polyline Encoder Utility | Google Maps APIs | Google Developers]]
([TIME[2016-07-13 06:14:40 +09:00]])
<https://developers.google.com/maps/documentation/utilities/polylineutility>
]FIGCAPTION]
> Polylines in Google Maps are formed as a set of latitude/longitude pairs. In addition, for each vertex (location) in an encoded polyline, a level can be specified indicating that the location should appear on that level and any level higher (i.e. any decrease in zoom.).
]FIG]
[7] [CITE[Geo::Google::PolylineEncoder - search.cpan.org]]
([TIME[2016-07-19 20:55:42 +09:00]])
<http://search.cpan.org/dist/Geo-Google-PolylineEncoder/lib/Geo/Google/PolylineEncoder.pm>
[FIG(quote)[
[FIGCAPTION[
[14] [CITE@en[Strava API Reference]]
( ([TIME[2016-07-26 09:24:09 +09:00]]))
<https://strava.github.io/api/#polylines>
]FIGCAPTION]
> Activity and segment API requests may include summary polylines of their respective routes. The values are string encodings of the latitude and longitude points using the Google encoded polyline algorithm format.
]FIG]
[16] [CITE@en[wakaba/perl-geo-encodedpolyline]]
([TIME[2016-10-04 20:23:13 +09:00]])
<https://github.com/wakaba/perl-geo-encodedpolyline>
[17] [CITE@en[wakaba/js-geo-encodedpolyline]]
([TIME[2016-10-04 22:15:15 +09:00]])
<https://github.com/wakaba/js-geo-encodedpolyline>
[18] [CITE[ST_AsEncodedPolyline]]
([TIME[2018-07-05 06:28:49 +09:00]])
<https://postgis.net/docs/ST_AsEncodedPolyline.html>