Bug #74303 for Algorithm-GooglePolylineEncoding: worse roundtrip performance

Most of it I hacked from http://www.usnaviguide.com/google-encode.htm .

"Dan Jacobson via RT" <bug-Algorithm-GooglePolylineEncoding@rt.cpan.org> writes: Show quoted text
Here's a patch: diff --git a/GooglePolylineEncoding.pm b/GooglePolylineEncoding.pm index 0d3fef3..14df217 100644 --- a/GooglePolylineEncoding.pm +++ b/GooglePolylineEncoding.pm @@ -72,14 +72,13 @@ sub encode_number { sub encode_polyline { my(@path) = @_; my @res; - my($curr_lat,$curr_lon) = do { my $first = shift @path; ($first->{lat}, $first->{lon}) }; - push @res, encode_number($curr_lat), encode_number($curr_lon); + my($curr_lat_e5,$curr_lon_e5) = (0,0); for my $lat_lon (@path) { - my($lat,$lon) = ($lat_lon->{lat}, $lat_lon->{lon}); - my $deltay = $lat - $curr_lat; - my $deltax = $lon - $curr_lon; + my($lat_e5,$lon_e5) = map { sprintf("%.0f", $_*1e5) } ($lat_lon->{lat}, $lat_lon->{lon}); + my $deltay = ($lat_e5 - $curr_lat_e5) / 1e5; + my $deltax = ($lon_e5 - $curr_lon_e5) / 1e5; push @res, encode_number($deltay), encode_number($deltax); - ($curr_lat,$curr_lon) = ($lat,$lon); + ($curr_lat_e5,$curr_lon_e5) = ($lat_e5,$lon_e5); } join '', @res; } -- Slaven Rezic - slaven <at> rezic <dot> de BBBike - route planner for cyclists in Berlin WWW version: http://www.bbbike.de Perl/Tk version for Unix and Windows: http://bbbike.sourceforge.net

Show quoted text
Show quoted text
Indeed, now the results are the same as you said! But I still think you can go further and beat all the other algorithms: Given A=Original points B=Rounded to five digits points Then take them for a round trip. Why can't we get back to B, and not just B+-1? Odd, if the input is already 5 digits long, then it comes back intact. Or something like that. OK, I'm not talking very clearly, but maybe you know what I mean.

$ perldoc -q \ round mentions half-way-point alternation... so forget all my sprintf stuff. Your way is better! OK, maybe there is no more roundtrip problem. #!/usr/bin/perl use strict; use warnings FATAL => 'all'; use Algorithm::GooglePolylineEncoding; my @encoded_polyline; my @decoded_polyline; while (<>) { if (/([0-9.]+),([0-9.]+)/) { push @{ $decoded_polyline[0] }, { lat => $2, lon => $1 }; } } for ( 0 .. 2 ) { $encoded_polyline[$_] = Algorithm::GooglePolylineEncoding::encode_polyline( @{ $decoded_polyline[$_] } ); print $encoded_polyline[$_], "\n"; @{ $decoded_polyline[ $_ + 1 ] } = Algorithm::GooglePolylineEncoding::decode_polyline( $encoded_polyline[$_] ); } for (@encoded_polyline) { use Digest::MD5 qw(md5 md5_hex md5_base64); print md5_hex($_), "\n"; }