Introduction

Google’s encoded polyline format compresses a list of latitude and longitude pairs into a short printable string. It is a compact transport format for routes and map overlays, and the algorithm is straightforward to implement in plain C once you understand the delta and bit-packing steps.

How the Encoding Works

Each coordinate pair goes through the same pipeline:

1. Multiply latitude and longitude by 100000.
2. Round to integers.
3. Store the difference from the previous point instead of the full value.
4. Left-shift the delta by one bit.
5. Invert the shifted number if the original delta was negative.
6. Emit the result in 5-bit chunks with 63 added to each chunk.

The delta step is what makes the format small. Adjacent route points are usually close together, so the change from one point to the next is much smaller than the absolute coordinate.

A Minimal Plain C Encoder

The following example encodes Google’s standard sample route:

1#include <math.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5typedef struct {
6    double lat;
7    double lng;
8} Point;
9
10static void encode_value(long value, char *out, size_t *index) {
11    value <<= 1;
12    if (value < 0) {
13        value = ~value;
14    }
15
16    while (value >= 0x20) {
17        out[(*index)++] = (char)((0x20 | (value & 0x1f)) + 63);
18        value >>= 5;
19    }
20
21    out[(*index)++] = (char)(value + 63);
22}
23
24char *encode_polyline(const Point *points, size_t count) {
25    long prev_lat = 0;
26    long prev_lng = 0;
27    size_t index = 0;
28    char *result = malloc(count * 24 + 1);
29
30    if (!result) {
31        return NULL;
32    }
33
34    for (size_t i = 0; i < count; i++) {
35        long lat = lround(points[i].lat * 1e5);
36        long lng = lround(points[i].lng * 1e5);
37
38        encode_value(lat - prev_lat, result, &index);
39        encode_value(lng - prev_lng, result, &index);
40
41        prev_lat = lat;
42        prev_lng = lng;
43    }
44
45    result[index] = '\0';
46    return result;
47}
48
49int main(void) {
50    Point points[] = {
51        {38.5, -120.2},
52        {40.7, -120.95},
53        {43.252, -126.453}
54    };
55
56    char *encoded = encode_polyline(points, 3);
57    if (!encoded) {
58        return 1;
59    }
60
61    printf("%s\n", encoded);
62    free(encoded);
63    return 0;
64}

Compile and run it:

cc -Wall -Wextra -O2 polyline.c -lm -o polyline
./polyline

Expected output:

_p~iF~ps|U_ulLnnqC_mqNvxq`@

Why the Negative-Value Step Matters

Most implementation bugs come from sign handling. The order is important:

1. compute the signed delta
2. left-shift it
3. invert the shifted value if the original delta was negative

If you invert before shifting, or if you encode absolute values instead of deltas, the output string may still look reasonable but will decode to the wrong route.

The same caution applies to rounding. The algorithm expects scaled integers, not raw floating-point values. If you truncate when you meant to round, points near half-step boundaries can drift.

Buffer Management in C

The example uses count * 24 + 1 bytes as a simple upper-bound buffer. That is fine for a small encoder demo because each point contributes two numbers and typical encoded chunks stay short. For production code, you may prefer a dynamically growing buffer to avoid guessing.

Even in a demonstration, three C-specific details matter:

• check malloc
• null-terminate the output
• free the buffer after use

These are not part of the polyline algorithm itself, but they are part of a correct C implementation.

Testing Your Output

Polyline code is easy to get almost right. That is why testing against known vectors matters more than intuition. A good minimal test checks both the expected string and a few edge cases:

1Point single[] = { {0.0, 0.0} };
2char *encoded = encode_polyline(single, 1);
3printf("%s\n", encoded);
4free(encoded);

Also test negative coordinates, repeated points, and long routes. If you later add a decoder, round-trip tests are even better: encode points, decode the string, and confirm the reconstructed coordinates match the originals within the expected precision.

Common Pitfalls

Forgetting the 1e5 scaling factor is a classic mistake. Without it, the encoded route is meaningless.

Another common error is encoding absolute coordinates instead of differences from the previous point. The algorithm depends on deltas for both correctness and compactness.

Memory handling causes a separate class of bugs in C versions. Underallocating the output buffer or forgetting the terminating null byte can make the encoder look broken even when the math is correct.

Finally, do not rely on visual inspection of the output string. Polyline strings are opaque by design, so use known examples and decoder checks.

Summary

• Encoded polyline stores scaled coordinate deltas, not raw latitude and longitude values.
• The sign-transform step for negative deltas is the most error-prone part.
• A small plain C encoder can reproduce Google’s sample output exactly.
• C implementations must handle allocation, termination, and freeing explicitly.
• Verify the algorithm with known sample routes before using it in production.