Google Maps Encoded Polyline Simplify

EncodedPolylineSimplify.php

<?php
namespace GoogleMaps;

/**
 * Utility class for simplifying Google encoded polylines.
 *
 * Example:
 * ```
 * use GoogleMaps\PolylineSimplifier;
 *
 * $simplified = PolylineSimplifier::simplify($encoded, 0.0003);
 * ```
 *
 * ----------------------------------------------
 * | epsilon   | effect                           
 * | --------- | -------------------------------- |
 * | `0.00005` | minimal simplification           |
 * | `0.0001`  | slightly simpler lines           |
 * | `0.0005`  | big reduction (ideal for routes) |
 * | `0.001`   | aggressive simplification        |
 */
class PolylineSimplifier
{
    /**
     * Takes an encoded polyline and returns a simplified encoded polyline.
     */
    public static function simplify(string $encodedPolyline, float $epsilon = 0.0002): string
    {
        $points = self::decode($encodedPolyline);
        $simplified = self::rdpSimplify($points, $epsilon);
        return self::encode($simplified);
    }

    /**
     * Decode Google's encoded polyline format.
     */
    private static function decode(string $encoded): array
    {
        $points = [];
        $index = 0;
        $lat = 0;
        $lng = 0;
        $len = strlen($encoded);

        while ($index < $len) {
            $shift = 0;
            $result = 0;

            do {
                $b = ord($encoded[$index++]) - 63;
                $result |= ($b & 0x1f) << $shift;
                $shift += 5;
            } while ($b >= 0x20);

            $dlat = (($result & 1) ? ~($result >> 1) : ($result >> 1));
            $lat += $dlat;

            $shift = 0;
            $result = 0;

            do {
                $b = ord($encoded[$index++]) - 63;
                $result |= ($b & 0x1f) << $shift;
                $shift += 5;
            } while ($b >= 0x20);

            $dlng = (($result & 1) ? ~($result >> 1) : ($result >> 1));
            $lng += $dlng;

            $points[] = [
                'lat' => $lat * 1e-5,
                'lng' => $lng * 1e-5
            ];
        }

        return $points;
    }

    /**
     * Encode array of lat/lng points into Google's encoded polyline format.
     */
    private static function encode(array $points): string
    {
        $lastLat = 0;
        $lastLng = 0;
        $encoded = "";

        foreach ($points as $p) {
            $lat = (int) round($p['lat'] * 1e5);
            $lng = (int) round($p['lng'] * 1e5);

            $encoded .= self::encodeDiff($lat - $lastLat);
            $encoded .= self::encodeDiff($lng - $lastLng);

            $lastLat = $lat;
            $lastLng = $lng;
        }

        return $encoded;
    }

    private static function encodeDiff(int $diff): string
    {
        $diff = $diff << 1;
        if ($diff < 0) {
            $diff = ~$diff;
        }

        $output = "";

        while ($diff >= 0x20) {
            $output .= chr((0x20 | ($diff & 0x1f)) + 63);
            $diff >>= 5;
        }

        $output .= chr($diff + 63);
        return $output;
    }

    /**
     * Ramer–Douglas–Peucker simplification.
     */
    private static function rdpSimplify(array $points, float $epsilon): array
    {
        $count = count($points);
        if ($count < 3) {
            return $points;
        }

        $dmax = 0;
        $index = 0;
        $start = $points[0];
        $end = $points[$count - 1];

        foreach ($points as $i => $p) {
            $d = self::perpendicularDistance($p, $start, $end);
            if ($d > $dmax) {
                $index = $i;
                $dmax = $d;
            }
        }

        if ($dmax > $epsilon) {
            $rec1 = self::rdpSimplify(array_slice($points, 0, $index + 1), $epsilon);
            $rec2 = self::rdpSimplify(array_slice($points, $index), $epsilon);
            return array_merge(array_slice($rec1, 0, -1), $rec2);
        }

        return [$start, $end];
    }

    private static function perpendicularDistance(array $p, array $a, array $b): float
    {
        $dx = $b['lng'] - $a['lng'];
        $dy = $b['lat'] - $a['lat'];

        if ($dx == 0 && $dy == 0) {
            return hypot($p['lng'] - $a['lng'], $p['lat'] - $a['lat']);
        }

        return abs(
            $dy * $p['lng'] - $dx * $p['lat'] +
            $b['lng'] * $a['lat'] - $b['lat'] * $a['lng']
        ) / sqrt($dx * $dx + $dy * $dy);
    }
}