What are the design decisions behind Google Maps encoded polyline algorithm format? -


several google maps products have notion of polylines, in terms of underlying data sequence of lat/lng points might example manifest in line drawn on map. google map developer libraries make use of encoded polyline format churns out ascii string representing points making polyline. encoded format typically decoded built in function of google libraries or function written third party implements decoding algorithm.

the algorithm encoding polyline points described in encoded polyline algorithm format document. is not described rationale implementing algorithm way, , significance of each of individual steps. i'm interested know whether thinking/purpose behind implementing algorithm way publicly described anywhere. 2 example questions:

  • do of steps have quantifiable impact on compression , how impact vary function of delta between points?
  • is summing of values ascii 63 compatibility hack of sort?

but in general, description go along algorithm explaining why algorithm implemented way is.

update: this blog post james snook has 'valid ascii' range argument , reads logically other steps wondered. e.g. left shifting before storing makes place negative bit first bit.

some explanations found, not sure if 100% correct.

  • one double value stored in multiple 5 bits chunks , 0x20 (binary '0010 0000') used indication next 5 bit entry belongs current double.
  • 0x1f (binary '0001 1111') used bit mask throw away other bits
  • i expect 5 bits used because delta of lat or lons in range. every double value takes 5 bits on average when done lot of examples (but not verified yet).
  • now, compression done assuming nearby double values close , creating difference 0, results fits in few bytes. result stored in dynamic fashion: store 5 bits , if value longer mark 0x20 , store next 5 bits , on. guess can tweak compression if try 6 or 4 bits guess 5 practically reasonable choice.
  • now regarding magic 63, 0x3f , binary 0011 1111. i'm not sure why add it. thought adding 63 give 'better' asci characters (e.g. allowed in xml or in url) skip e.g. 62 > 63 ? better? @ least first ascii chars not displayable , have avoided. note if 1 use 64 1 hit ascii char 127 maximum value of 31 (31+64+32) , char not defined in html4. or because of signed char going -128 127 , need store negative numbers positive, adding maximum possible negative number?
  • just me: here link official java implementation apache license

Comments

Post a Comment

Popular posts from this blog

basic authentication with http post params android -

i doing basic authentication passing username , password , using basicnamevaluepair sending post params response service. my method: public stringbuilder callservicehttppost(string username, string password, string type) { // create new httpclient , post header httpclient httpclient = new defaulthttpclient(); httppost httppost = new httppost(webservice + type); httpresponse response = null; stringbuilder total = new stringbuilder(); try { url url = new url(webservice + type); /*string base64encodedcredentials = base64.encodetostring((username + ":" + password).getbytes(), base64.url_safe | base64.no_wrap);*/ string base64encodedcredentials = "basic " + base64.encodetostring( (username + ":" + password).getbytes(), base64.no_wrap); httppost.setheader("auth...
Read more

vb.net - Virtual Keyboard commands -

i wondering difference between virtual these keyboard commands is: keyeventf_extendedkey , keyeventf_keyup is. everywhere have looked gives me description based off integers , not want know each of them does. you've tagged question vb.net, these have nothing @ vb.net. they're constants defined in windows header files, use win32 api functions. as far difference, can't tell looking @ values. individual values not particularly important, that's why named identifiers used. what's important used , documentation functions tells mean. the first one, keyeventf_extendedkey , used keybdinput structure (which used along e.g. sendinput function) pass information synthesized keyboard input. if flag used, means scan code should interpreted extended key. technically, means scan code preceded prefix byte value 224 (&he0 in hexadecimal notation). the second one, keyeventf_keyup , 1 of flags available use structure. means key being released (going up)...
Read more

How to get multiresult with multicondition in Sql Server -

i need solve this. hopefully can giving me advices. for sample, i've got data : proclib.march 1 first 10 rows flight date depart orig dest miles boarded capacity ----------------------------------------------------------------- 114 01mar94 7:10 lga lax 2475 172 210 202 01mar94 10:43 lga ord 740 151 210 219 01mar94 9:31 lga lon 3442 198 250 622 01mar94 12:19 lga fra 3857 207 250 132 01mar94 15:35 lga yyz 366 115 178 271 01mar94 13:17 lga par 3635 138 250 302 01mar94 20:22 lga 229 105 180 114 02mar94 7:10 lga lax 2475 119 210 202 02mar94 10:43 lga ord 740 120 210 219 02mar94 9:31 lga lon 344...
Read more