Compressed Lat/Lng Encoding/Decoding
MapQuest Platform Services use a slight variant of the Google Polyline Encoding Format. The MapQuest Platform Services variant of the algorithm allows for arbitrary precision of encoded data. The default precision for encoded data is 5 digits (as with the Google format), but MapQuest line data is often accurate to 6 digits of precision.
Note that the precision used during encoding must be the same as the precision used during decoding, or your data will decompress to values which are off by orders of magnitude from the input data!
Contents
JavaScript Sample Source
function decompress (encoded, precision) {
precision = Math.pow(10, -precision);
var len = encoded.length, index=0, lat=0, lng = 0, array = [];
while (index < len) {
var b, shift = 0, result = 0;
do {
b = encoded.charCodeAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
var dlat = ((result & 1) ? ~(result >> 1) : (result >> 1));
lat += dlat;
shift = 0;
result = 0;
do {
b = encoded.charCodeAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
var dlng = ((result & 1) ? ~(result >> 1) : (result >> 1));
lng += dlng;
array.push(lat * precision);
array.push(lng * precision);
}
return array;
}
function compress(points, precision) {
var oldLat = 0, oldLng = 0, len = points.length, index = 0;
var encoded = '';
precision = Math.pow(10, precision);
while (index < len) {
// Round to N decimal places
var lat = Math.round(points[index++] * precision);
var lng = Math.round(points[index++] * precision);
// Encode the differences between the points
encoded += encodeNumber(lat - oldLat);
encoded += encodeNumber(lng - oldLng);
oldLat = lat;
oldLng = lng;
}
return encoded;
}
function encodeNumber(num) {
var num = num << 1;
if (num < 0) {
num = ~(num);
}
var encoded = '';
while (num >= 0x20) {
encoded += String.fromCharCode((0x20 | (num & 0x1f)) + 63);
num >>= 5;
}
encoded += String.fromCharCode(num + 63);
return encoded;
}
ActionScript Sample Source
public function doDecode(encodedString:String,precision:String):LatLngCollection {
var encoded:String = new String(encodedString);
var len:int = encoded.length;
var index:int = 0;
var llc:LatLngCollection = new LatLngCollection();
var lat:int = 0;
var lng:int = 0;
try
{
while (index < len) {
var b:int;
var shift:int = 0;
var result:int = 0;
do {
b = encoded.charCodeAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
var dlat:int = ((result & 1) ? ~(result >> 1) : (result >> 1));
lat += dlat;
shift = 0;
result = 0;
do {
b = encoded.charCodeAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
var dlng:int = ((result & 1) ? ~(result >> 1) : (result >> 1));
lng += dlng;
var ll:LatLng;
switch (precision) {
case PRECISION_6:
ll = new LatLng((lat * 1e-6), (lng * 1e-6));
break;
case PRECISION_5:
ll = new LatLng((lat * 1e-5), (lng * 1e-5));
break;
}
llc.add(ll);
}
}
catch(e:Error) {
throw new Error ("A decode error has occurred.");
}
return llc;
}
//Create the encoded bounds.
public function doEncode(points:LatLngCollection,precision:String):String {
var plat:int = 0;
var plng:int = 0;
var encoded_points:String = "";
for(var i:int = 0; i < points.size; i++) {
var point:LatLng = points.getLatLng(i);
var lat:Number = point.lat;
var lng:Number = point.lng;
var late5:Number;
var lnge5:Number;
switch (precision) {
case PRECISION_6:
late5 = Math.floor(lat * 1e6);
lnge5 = Math.floor(lng * 1e6);
break;
case PRECISION_5:
late5 = Math.floor(lat * 1e5);
lnge5 = Math.floor(lng * 1e5);
break;
}
var dlat:Number = late5 - plat;
var dlng:Number = lnge5 - plng;
plat = late5;
plng = lnge5;
encoded_points += encodeSignedNumber(dlat) + encodeSignedNumber(dlng);
}
return encoded_points;
}
// Encode a signed number in the encode format.
private function encodeSignedNumber(num:Number):String {
var sgn_num:Number = num << 1;
if (num < 0) {
sgn_num = ~(sgn_num);
}
return(encodeNumber(sgn_num));
}
// Encode an unsigned number in the encode format.
private function encodeNumber(num:Number):String {
var encodeString:String = "";
while (num >= 0x20) {
encodeString += (String.fromCharCode((0x20 | (num & 0x1f)) + 63));
num >>= 5;
}
encodeString += (String.fromCharCode(num + 63));
return encodeString;
}
Interactive Example
| Collection | Encoded | Decoded |
|---|---|---|
Precision:
