An arcencode example

Arcencode is my Tcl implementation of the compression algorithm used by both MapQuest and the Google Maps API to encode a list of coordinates as a printable string. It can be used, for example, to obtain a relatively compact representation of a route that can be passed as a single parameter value to a web map.

Here is a GPX file exported from a map created with MapMyRun. It contains a track representing a route through a nearby park, pictured above. The track consists of 790 points, listed here in plain text form. If the contents of that plain text coordinate list are assigned to a variable named coordinates, the encoded form can be obtained with:

set encoded [arcencode $coordinates]

With line breaks added, the contents of encoded are:

q}g`GrlfnMPDND\DJ?L?T?P?N?N?N?P?VAPANANAPANAPANATGNELGXENANANCNANA^BNDPDNBNDNDND
NDPDNDNBNDNDPDNDNDNDVHNFPFNFNFNFPFNFNFNFPFNFNFNFPFNDNFNFPFNFNFNFVFNBPBNBNBNBVFND
PDNDPDNFPDNDPDNDPDNDPDNDPDNDPDNFPDNDPDNFPFNDPFNFPFNDPFNFPFNDZLHFJDNFPHNFNHPFNH\F
LAJ?V?F?PFNFNDNFNHZNLHNHLHLHLHNJLHLHT?N?PAN?PAPAVDPFNDNDPDNFNDPDNDNFPDNDPDNFNDPD
ND\JLDNBNDLDNDNBTFNDLBLDVDN@PBN@PBN@PBNBP@XHNHLFNHNFNFLHNFNFPVBNPVJFHHRLHFPANCPC
PAPAR?L@R@P@P?N@P@P@P@P@VFLDLFRHNFNFPFNFNFNFNFNFNFTLHFLPLNJLRTJHPJJDPBTAJCPGPGNE
PGNGPGNGNEPGNGPGNEPGNGNGPGNEPGZIJAJAVJLDLDRAPENCPCNCPENCPCNEPCXGNCLCNCNCPDPHTTJJ
HLHJLNJLLLRLLBPFRNJLJJJLJLTHL@T@L?N@THLHLHLHNLNJLLLJNJ\LL@N@N@L?N@ZALENCLCNENCRI
NGNELGZKNGNGNGNGNGNGNENGNGNGNGNGNGNGTUFQHOHOFQN[HOFMPYHKHINQJKLLHRHPHPHRJPHPHRHP
J^BPDRDPDVJVHNHPPNNJLHLHLJRFPFNDNDPFNDNDPFXHLFLDLDRFNFNDNDRBNBN@RENCPEPCNEXCH@P@
VJJHHHFBEWCSEUGSIUO[KOIMIMUWKMMKMMKMMMMKKMMMMMSMOGMIOIOGOIYQMIMIMGMIKIUMMKOIOKMI
OIOKMIOIOKOISKOEMGOEUCOCQAOAQCQAYCMAMCSEOEOEQCOEWCM@WBMBOBODOBUJMFMHMHMLOJMLWPMF
MFMFWFMBOBODYBO@O?O@O@O@SCOAOCQEOEQEQEOGQEOGWGMAU?M@O@QDODQBWFQBOBO@QBOBOBQBOBSB
O@QB[DOBOBODOBOBOBOBUDQDOBOBQDOBOBW?KEQGMGQ@QBQFOD_@NODOFODOFOFODOFODOFODOFOFODO
FODYJK@Q?SGKCOMKKQQKMKOKMOKUMOGOGOGOGOGOGOGQGOGWKIEOGWEQ?OAQAOAQ?OAQAOAQ?W?SGIIK
GKOKQMOOMMISCUHGFQGOGOIOGOIOGOIQIOGUGQAOCQAOCQAOCQAOC[GOEOEQEOCOEOEOEOEOEOESEOGQ
EOEQGOEQEOEQGUGOEQGOEOEOEQGOEU?Q?O@Q?O@O@YIOIMKMIOIMIOIMIMKQGQGOGOGOGYEM?M?Q@[GM
GOGMGMGMGUIMGOGWMKEMCQIQEOGOGQEOGOGOGQE[KQEOEOEQEOEOEQEOEOEQEOEOEQEOEOEQEOGOEQEO
EWEOCQCOEOCOC_@KOGOGOGOEOGOGQGOGOGOGOGOGOGOEOGOGOGOGOGOGOGWGOEQEOEQEOEQEOEQEOEQE
OEQEOEQEOE[AK@M@Q@Q@OBQ@QFOFOFWBO@Q@O@Q@O@Q@Q@U?O?Q?Q?O?Q?Q?O?]CKEMCME

Succinct, considering it encodes detailed geometry. A coordinate list of 790 corresponding points can be recovered from this block of text with the complementary arcdecode procedure:

set decoded [arcdecode $encoded]

The decoded coordinate list can be examined here.

An important proviso: this encoding scheme is lossy. Specifically, coordinate values are rounded to five decimal places. Compare the input coordinates to the decoded output for an example. Any precision can optionally be specified, but greater precision compromises the amount of compression. (Note that the Google Maps API is only compatible with five-digit precision).

How does this algorithm work? Google offers a technical step-by-step explanation. Essentially, compression is achieved by storing only the difference between each coordinate value and the previous value in the sequence; this requires fewer digits than storing each value in full, especially since precision is limited to a fixed number of digits. The values are packed into a printable Base64 representation in a way that eliminates the need for delimiters between coordinate values: values are bit-shifted left before output, and the ones place is used to mark whether the subsequent character represents a new coordinate or a continuation of the same value.

I updated my WheresThatSat site to use JavaScript and (on the Twitter bot side) Ruby implementations of this algorithm. It’s an appropriate application – previously, satellite ground tracks were encoded as a repetitive sequence of separate point parameters. In addition to yielding somewhat shorter URLs, this compression method ensures the correct point sequence is preserved even if the URL parameters are re-ordered.

Posted on Sunday, March 3rd, 2013.