The Polyline Algorithm

I got a confusing API response from a Routing API a few days back. It was a route from point A to point B, about 200 stops in between, and buried in the JSON was this weird-looking string:

_p~iF~ps|U_ulLnnqC_mqNvxq`@

My first thought was that something had gone wrong. Encoding issue? Corrupted payload? Nope. Turns out, that string was the route. Three latitude-longitude pairs, compressed into just 27 characters of ASCII. This is Google's Encoded Polyline Algorithm Format at work, and it's what most mapping APIs return when they hand you a route geometry.

I'm currently working on a Route Planning feature at NextBillion.ai and Velocitor Solutions: you give it a list of pickup and delivery locations, and it spits back an optimized route for a fleet of drivers to follow. The route geometry comes back as a polyline, and until I actually sat down to understand the encoding, it genuinely felt like magic.

But of course, it's not magic. It's just clever bit manipulation that makes route information incredibly lightweight.

Why Bother Compressing Coordinates?

Imagine this, you've got a route with a 1000 points, all encoded as JSON coordinate pairs.. about 50 KB easily. That's before gzip, sure, but it's still a lot of redundant data flying over the network (especially when you're serving millions of route requests a day).

Polyline encoding gets that down to a fraction of the size. The string _p~iF~ps|U_ulLnnqC_mqNvxq`@ encodes three full coordinate pairs in 27 characters.

The equivalent JSON would be:

[[38.5, -120.2], [40.7, -120.95], [43.252, -126.453]]

That's 52 characters, almost double. And the gap widens as routes get longer.

The secret sauce? Delta Encoding.

Delta Encoding: The Real Trick

After the first point, every subsequent point is actually stored as an offset from the previous one. If your route follows a highway, consecutive points are almost always close together.

Small deltas mean small numbers, and small numbers mean fewer characters. See what we're getting at?

Play with the widget below. Try switching between "Google's Example" (spread-out points) and "Highway Route" or "City Blocks" (points that are meters apart). Watch how the delta values shrink:

The red bars show what you'd have to encode if you sent absolute coordinates. The teal bars show delta values, the actual numbers that get encoded. On a real-world route where points are a few meters apart, those deltas are tiny.

How Polyline Encoding Works

So how does a number like -179.9832104 turn into `~oia@? The process has a few steps, and it's easier to watch than to read about. Enter a coordinate value below and hit "Encode":

The actual steps:

1. Scale to integers: Multiply by 100,000 to get 5 decimal places of precision (~1.1 meters at the equator). Floats become integers.

2. Zig-zag encoding: Left-shift by one bit, then invert if negative. This puts the sign information in the least-significant bit, so small absolute values (whether positive or negative) produce small encoded values.

3. Variable-length chunks: Break into 5-bit pieces, because smaller numbers need fewer chunks. Also, the sixth bit signals "more chunks coming."

4. ASCII output: Add 63 to each chunk and convert it to a character. This transforms everything into the printable ASCII range (63-126). Safe for JSON, URLs, and basically any text transport.

How To Decode A Polyline

The first time I ran a decoder on that cryptic string and watched actual coordinates pop out, coordinates I could plot on a map, it genuinely felt like watching a magic trick.

Paste any encoded polyline below (or use the default, which is Google's example) and watch it decode:

Notice how the string gets "consumed" left to right? Each point takes a variable number of characters depending on how big the delta values are.

Precision: Polyline5 vs Polyline6

The classic algorithm multiplies coordinates by 1e5 before encoding. Five decimal places, roughly 1.1 meters of precision at the equator. This is what most people mean when they say "polyline", sometimes called polyline5.

There's a variant called polyline6 that multiplies by 1e6 instead. Six decimal places, ~11 centimeters of precision. Dude. That's overkill for most consumer use cases, but the right choice for lane-level navigation, drone flight paths, or anything where sub-meter precision matters.

The tradeoff is that every chunk gets a bit larger, of course, so your encoded strings run a bit longer.

Mapbox uses polyline6 by default. Google, HERE, and most Routing APIs stick with polyline5. If you're working with these service and see decoded coordinates that look wildly off (like your points are hundreds of kilometers from where they should be), check whether the API returned polyline5 or polyline6 and adjust your divisor accordingly.

Why This Matters for Route Planning

At Velocitor, we're optimizing delivery routes for fleets. Think dozens of stops, hundreds of miles, routes that need to render on a driver's phone in milliseconds. The route optimization API returns the geometry as a polyline, the frontend decodes it, and Leaflet (or Google Maps, or Mapbox) draws it on the map.

The compression isn't just a nice-to-have. When you're serving thousands of concurrent drivers, each requesting route updates as traffic conditions change, the difference between 50 KB and 5 KB per response adds up. Polyline encoding is one of those invisible optimizations that makes the whole system feel snappy without anyone noticing it's there.

By the way, the actual algorithm is from the early 2000s. It's been in Google Maps since before smartphones existed.. And it's still the standard.

Small output, quick to encode and decode, survives any text transport. Sometimes, the boring solution is the right one. :)

If you liked this piece and want more of the same kind of low-level engineering deep-dive, I did a similar walk-through on how I rebuilt ISRO's satellite imagery viewer with better UX and IndexedDB caching.

Common Questions

What is the Polyline Algorithm?
The Polyline Algorithm is Google's Encoded Polyline Algorithm Format, a lossy compression scheme that turns a sequence of latitude/longitude coordinates into a short ASCII string. It combines delta encoding, zig-zag encoding, and variable-length 5-bit chunks to fit route geometry into a fraction of the space raw JSON would take.

How does polyline encoding actually work?
Each coordinate gets multiplied by 100,000 and rounded to an integer (giving ~1.1 metres of precision), then stored as an offset from the previous coordinate. Those integers get zig-zag encoded so small negatives stay small, then split into 5-bit chunks with a continuation bit and shifted into the printable ASCII range by adding 63.

What's the difference between polyline5 and polyline6?
Polyline5 multiplies coordinates by 100,000 for ~1.1 metres of precision. This is the classic Google Maps format. Polyline6 multiplies by 1,000,000 for ~11 centimetres of precision, at the cost of slightly longer encoded strings. Google, HERE and most routing APIs use polyline5; Mapbox and some newer APIs default to polyline6.

Is polyline encoding lossy?
Yes. Multiplying by 100,000 and rounding drops anything past five decimal places, which caps precision at roughly 1.1 metres at the equator. That's well below consumer GPS accuracy, so for most mapping use cases the loss is invisible.

How do I decode a polyline in JavaScript?
The @mapbox/polyline npm package is the community standard. Call polyline.decode(encoded) to get an array of [lat, lng] pairs. Most mapping libraries (Leaflet, Mapbox GL, Google Maps JS SDK) also accept encoded polylines directly, so you often don't need to decode manually.

Why do routing APIs return polylines instead of JSON arrays?
For a route with a few thousand points, an encoded polyline is roughly 8-10x smaller than the equivalent JSON array of coordinate pairs. When you're serving many concurrent route requests over mobile connections, that size difference dominates response time and bandwidth cost.

Can I use polyline encoding for things other than routes?
Yes. Any sequence of (lat, lng) points that tends to be close together compresses well: hiking trails, ship tracks, delivery zones, geofences, drone flight paths, animal migration data, and so on.

References

1. Google Developers. Encoded Polyline Algorithm Format. Google Maps Platform Documentation. https://developers.google.com/maps/documentation/utilities/polylinealgorithm

2. Goldstein, M. et al. (2013). An Analysis of the Lempel-Ziv and Burrows-Wheeler Transform Families for Geospatial Data Compression. Discusses delta encoding as a pre-processing step for coordinate compression.

3. Protocol Buffers. Encoding: Signed Integers. Google Developers. https://protobuf.dev/programming-guides/encoding/#signed-ints. The "zig-zag" encoding technique used in polylines originated here.

4. Mapbox. Polyline. npm package documentation. https://github.com/mapbox/polyline. A widely-used JavaScript implementation.

5. Mapbox. Directions API: Route Geometry. https://docs.mapbox.com/api/navigation/directions/#route-geometry. Documents polyline6 as the default geometry format for the Mapbox Directions API.

6. RFC 4648. The Base16, Base32, and Base64 Data Encodings. IETF. https://datatracker.ietf.org/doc/html/rfc4648. Background on ASCII-safe binary encoding schemes.

Join the newsletter

Get notified when I publish something new. No spam, unsubscribe anytime.

Subscribe