Geo-Google-PolylineEncoder

 view release on metacpan or  search on metacpan

lib/Geo/Google/PolylineEncoder.pm  view on Meta::CPAN

=head1 NAME

Geo::Google::PolylineEncoder - encode lat/lons to Google Maps Polylines

=head1 SYNOPSIS

  use Geo::Google::PolylineEncoder;

  my $points = [
                # can also take points as [lat, lon]
		{ lat => 38.5, lon => -120.2 },
	        { lat => 40.7, lon => -120.95 },
	        { lat => 43.252, lon => -126.453 },
	       ];
  my $encoder = Geo::Google::PolylineEncoder->new;
  my $eline   = $encoder->encode( $points );
  print $eline->{num_levels};  # 18
  print $eline->{zoom_factor}; # 2
  print $eline->{points};      # _p~iF~ps|U_ulLnnqC_mqNvxq`@
  print $eline->{levels};      # POP

  # in Javascript, assuming eline was encoded as JSON:
  # ... load GMap2 ...
  var opts = {
    points: eline.points,
    levels: eline.levels,
    numLevels: eline.num_levels,
    zoomFactor: eline.zoom_factor,
  };
  var line = GPolyline.fromEncoded( opts );

=cut

package Geo::Google::PolylineEncoder;

use strict;
use warnings;

use accessors qw(num_levels zoom_factor visible_threshold force_endpoints
		 zoom_level_breaks escape_encoded_points lons_first
		 points dists max_dist encoded_points encoded_levels );
use constant defaults => {
			  num_levels  => 18,
			  zoom_factor => 2,
			  force_endpoints => 1,
			  escape_encoded_points => 0,
			  visible_threshold => 0.00001,
			  lons_first => 0,
			 };
our $VERSION = 0.06;

# The constructor
sub new {
    my $class = shift;
    my $self = bless {}, $class;
    $self->init(@_);
    return $self;
}

sub init {
    my ($self, %args) = @_;

    foreach my $attr (keys %{ $self->defaults }) {
	$self->$attr($self->defaults->{$attr});
    }

    foreach my $attr (keys %args) {
	$self->$attr($args{$attr});
    }
}

sub init_zoom_level_breaks {
    my $self = shift;

    # Cache for performance:
    my $num_levels = $self->num_levels;

    my @zoom_level_breaks;
    for my $i (1 .. $num_levels) {
	push @zoom_level_breaks,
	  $self->visible_threshold * $self->zoom_factor ** ($num_levels - $i);
    }

    $self->zoom_level_breaks(\@zoom_level_breaks);
}

sub reset_encoder {
    my $self = shift;
    $self->points([])->dists([])->max_dist(0)->encoded_points('')->encoded_levels('');
    # Note: calculate zoom level breaks here in case num_levels, etc. have
    # changed between encodes:
    $self->init_zoom_level_breaks;
}

sub set_points {
    my ($self, $points) = @_;

    die "points must be an arrayref!" unless UNIVERSAL::isa( $points, 'ARRAY' );

    # Internally, points are stored as [lat, lon].  Although this is less
    # readable, it is more efficient than using a hash.

    # Make a copy of the points we were given
    my @points;
    if (UNIVERSAL::isa($points->[0], 'HASH')) {

lib/Geo/Google/PolylineEncoder.pm  view on Meta::CPAN

    $self->dists( \@dists )->max_dist( $max_dist );
} # calculate_distances


# The encode_points function is very similar to Google's
# http://www.google.com/apis/maps/documentation/polyline.js
# The key difference is that not all points are encoded,
# since some were eliminated by Douglas-Peucker.
sub encode_points {
    my $self = shift;
    my $points = $self->points;
    my $dists  = $self->dists;

    my $encoded_points = "";
    my $oldencoded_points = "";
    my ($last_lat, $last_lon) = (0.0, 0.0);

    for (my $i = 0; $i < @$points; $i++) {
	my $point = $points->[$i];
	my $lat = $point->[0];
	my $lon = $point->[1];

	if (defined($dists->[$i]) || $i == 0 || $i == @$points - 1) {
	    # compute deltas, rounded to 5 decimal places:
	    my $lat_e5    = sprintf('%.5f', $lat)+0; # round()
	    my $lon_e5    = sprintf('%.5f', $lon)+0; # round()
	    my $delta_lat = sprintf('%.5f', $lat_e5 - $last_lat)+0;
	    my $delta_lon = sprintf('%.5f', $lon_e5 - $last_lon)+0;
	    ($last_lat, $last_lon) = ($lat_e5, $lon_e5);

	    $encoded_points .=
	      $self->encode_signed_number($delta_lat) .
	      $self->encode_signed_number($delta_lon);
	} else {
	    # warn "skipping point: $lat, $lon";
	}
    }

    $self->encoded_points( $encoded_points );
}


# Use compute_level to march down the list of points and encode the levels.
# Like encode_points, we ignore points whose distance (in dists) is undefined.
# See http://code.google.com/apis/maps/documentation/polylinealgorithm.html
sub encode_levels {
    my $self = shift;
    my $points = $self->points;
    my $dists  = $self->dists;
    my $max_dist = $self->max_dist;

    # Cache for performance:
    my $num_levels = $self->num_levels;
    my $num_levels_minus_1 = $num_levels - 1;
    my $visible_threshold = $self->visible_threshold;
    my $zoom_level_breaks = $self->zoom_level_breaks;

    my $encoded_levels = "";

    if ($self->force_endpoints) {
	$encoded_levels .= $self->encode_number($num_levels_minus_1);
    } else {
	$encoded_levels .= $self->encode_number($num_levels_minus_1 - $self->compute_level($max_dist));
    }


    # Note: skip the first & last point:
    for my $i (1 .. scalar(@$points) - 2) {
	my $dist = $dists->[$i];
	if (defined $dist) {
	    # Note: brought compute_level in-line as it was performing *really* slowly
	    #
	    # This computes the appropriate zoom level of a point in terms of it's
	    # distance from the relevant segment in the DP algorithm.  Could be done
	    # in terms of a logarithm, but this approach makes it a bit easier to
	    # ensure that the level is not too large.
	    #my $level = $self->compute_level($dist);
	    my $level = 0;
	    if ($dist > $visible_threshold) {
		while ($dist < $zoom_level_breaks->[$level]) {
		    $level++;
		}
	    }

	    $encoded_levels .= $self->encode_number($num_levels_minus_1 - $level);
	}
    }

    if ($self->force_endpoints) {
	$encoded_levels .= $self->encode_number($num_levels_minus_1);
    } else {
	$encoded_levels .= $self->encode_number($num_levels_minus_1 - $self->compute_level($max_dist));
    }

    $self->encoded_levels( $encoded_levels );
}


# This computes the appropriate zoom level of a point in terms of it's
# distance from the relevant segment in the DP algorithm.  Could be done
# in terms of a logarithm, but this approach makes it a bit easier to
# ensure that the level is not too large.
sub compute_level {
    my ($self, $dist) = @_;

    # Cache for performance:
    my $zoom_level_breaks = $self->zoom_level_breaks;

    my $level;
    if ($dist > $self->visible_threshold) {
	$level = 0;
	while ($dist < $zoom_level_breaks->[$level]) {
	    $level++;
	}
    }

    return $level;
}

# Based on the official google example
# http://code.google.com/apis/maps/documentation/include/polyline.js
sub encode_signed_number {
    my ($self, $orig_num) = @_;

    # 1. Take the initial signed value:
    # 2. Take the decimal value and multiply it by 1e5, rounding the result:

    # Note 1: we limit the number to 5 decimal places with sprintf to avoid
    # perl's rounding errors (they can throw the line off by a big margin sometimes)
    # From Geo::Google: use the correct floating point precision or else
    # 34.06694 - 34.06698 will give you -3.999999999999999057E-5 which doesn't
    # encode properly. -4E-5 encodes properly.

    # Note 2: we use sprintf(%.0f ...) rather than int() for similar reasons
    # (see perldoc -f int), though there's not much in it and the sprintf approach
    # ends up doing more of a round() than a floor() in some cases:
    #   floor = -30   num=-30 *int=-29  1e5=-30  %3.5f=-0.00030  orig=-0.000300000000009959
    #   floor = 119  *num=120  int=119  1e5=120  %3.5f=0.00120   orig=0.0011999999999972

    # Note 3: We don't use floor() to avoid a dependency on POSIX.  And it
    # doesn't round() anyway.

    # do this in a series of steps so we can see what's going on in the debugger:
    my $num3_5  = sprintf('%.5f', $orig_num)+0; # round at 5 decimal places
    my $num_1e5 = $num3_5 * 1e5;
    my $num      = sprintf('%.0f', $num_1e5)+0; # think int(...)

    # RT 49327: the signedness has to be determined *after* rounding
    my $is_negative = $num < 0;

lib/Geo/Google/PolylineEncoder.pm  view on Meta::CPAN

	    do {
		$b = ord( substr( $encoded, $index++, 1 ) ) - 63;
		$result |= ($b & 0x1f) << $shift;
		$shift += 5;
	    } while ($b >= 0x20);
	    my $dlon = $result >> 1;
	    if ($result & 1) {
		use integer; # force 2's complement
		$dlon = ~$dlon;
	    }
	    $lon += $dlon;
	}

	push @array, { lat => $lat * 1e-5, lon => $lon * 1e-5 };
    }

    return \@array;
}

# Decode an encoded levels string into a list of levels.
# adapted from http://code.google.com/apis/maps/documentation/include/polyline.js
sub decode_levels {
    my ($class, $encoded) = @_;

    my $len = length( $encoded );
    my @levels;

    for (my $index = 0; $index < $len; $index++) {
	my $level = ord( substr( $encoded, $index, 1 ) ) - 63;
	push @levels, $level;
    }

    return \@levels;
}


1;

__END__

=head1 DESCRIPTION

This module encodes a list of lat/lon points representing a polyline into a
format for use with Google Maps.  This format is described here:

L<http://code.google.com/apis/maps/documentation/polylinealgorithm.html>

The module is a port of Mark McClure's C<PolylineEncoder.js> with some tweaks.
The original can be found here:

L<http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/>

=head1 CONSTRUCTOR & ACCESSORS

=over 4

=item new( [%args] )

Create a new encoder.  Arguments are optional and correspond to the accessor
with the same name: L</num_levels>, L</zoom_factor>, L</visible_threshold>,
L</force_endpoints>, etc...

Note: there's nothing stopping you from setting these properties each time you
L</encode> a polyline.

=item num_levels

How many different levels of magnification the polyline has.
Default: 18.

=item zoom_factor

The change in magnification between those levels (see L</num_levels>).
Default: 2.

=item visible_threshold

Indicates the length of a barely visible object at the highest zoom level.
Default: 0.00001.  err.. units.

=item force_endpoints

Indicates whether or not the endpoints should be visible at all zoom levels.
force_endpoints is.  Probably should stay true regardless.
Default: 1=true.

=item escape_encoded_points

Indicates whether or not the encoded points should have escape characters
escaped, eg:

  $points =~ s/\\/\\\\/g;

This is useful if you'll be evalling the resulting strings, or copying them into
a static document.

B<Warning:> don't turn this on if you'll be passing the encoded points straight
on to your application, or you'll get unexpected results (ie: lines that start
out right, but end up horribly wrong).  It may even crash your browser.

Default: 0=false.

=item lons_first

Specifies the order in which coordinates passed as arrayrefs to L</encode> should be
interpreted:

  # false: lat, lon
  $encoder->encode([
     [ 38.5, -120.2 ],
     [ 40.7, -120.95 ],
  ]);

  # true: lon, lat
  $encoder->encode([
     [ -120.2, 38.5 ],
     [ -120.95, 40.7 ],
  ]);

Default: 0 = lat,lon

(Yes, the default feels wrong to the mathematician in me, but that's how Google
Maps do it, so for sake of consistency...)

=back

=head1 METHODS

=over 4

=item encode( \@points );

Encode the points into a string for use with Google Maps C<GPolyline.fromEncoded>
using a variant of the Douglas-Peucker algorithm to set levels, and the Polyline
encoding algorithm defined by Google.

Expects a reference to a C<@points> array:

  [
   { lat => 38.5, lon => -120.2 },
   { lat => 40.7, lon => -120.95 },
   { lat => 43.252, lon => -126.453 },
  ];