Point Compression Algorithm
Note
Bing Maps Elevations API retirement
Bing Maps Elevations API is deprecated and will be retired. Free (Basic) account customers can continue to use Bing Maps Elevations API until June 30th, 2025. Enterprise account customers can continue to use Bing Maps Elevations API until June 30th, 2028. To avoid service disruptions, all implementations using Bing Maps Elevations API will need to be updated to use an alternative solution, such as Create elevation data & services, by the retirement date that applies to your Bing Maps for Enterprise account type.
When the number of points (latitude and longitude pairs) becomes too large, the length of the URL request may exceed limits imposed by clients, proxies, or the server. To reduce the size of the request or when you cannot use the HTTP POST method, you can implement the compression algorithm described below to get a compressed string that you can use instead of the lengthy points list. The points parameter in the Elevation API URLs supports these compressed strings and automatically returns uncompressed elevation data. There is no need for a decompression algorithm.
This algorithm is best for 400 points or less. If you are requesting elevation data for more than 400 points, make an HTTP POST request.
The following example shows the difference in size between a list of points and the equivalent compressed string.
Original Values
points=35.894309002906084,-110.72522000409663,35.893930979073048,-110.72577999904752,35.893744984641671,-110.72606003843248,35.893366960808635,-110.72661500424147
Equivalent Compressed Value
points=vx1vilihnM6hR7mEl2Q
The following example shows how to use this encoded value as the points value when you request elevation values along a polyline path.
http://dev.virtualearth.net/REST/v1/Elevation/Polyline?points=vx1vilihnM6hR7mEl2Q&samples=20&heights=sealevel&key={BingMapsKey}
Algorithm Description
The following step-by-step instructions describe the point compression algorithm complete with an example. A test URL that you can use with a small number of points to test your algorithm implementation is described in Testing Your Algorithm Implementation, and a JavaScript Implementation is provided.
Start with a set of latitude and longitude values.
Lat Lon 35.894309002906084 -110.72522000409663 35.893930979073048 -110.72577999904752 35.893744984641671 -110.72606003843248 35.893366960808635 -110.72661500424147 Multiply each value by 100000 and round each result to the nearest integer.
Lat Lon 3589431 -11072522 3589393 -11072578 3589374 -11072606 3589337 -11072662 Calculate the difference between every pair of values. If a longitude difference exceeds +18000000 or -18000000, add or subtract 36000000 from the value.
If your set of points spans a path that is greater than 180 degrees, divide the path into multiple segments so that no individual segment exceeds 180 degrees.
Lat Lon 3589431 -11072522 -38 -56 -19 -28 -37 -56 Multiply each value by 2.
Lat Lon 7178862 -22145044 -76 -112 -38 -56 -74 -112 If any value is negative, change it to be a positive value, and then subtract 1.
Lat Lon 7178862 22145043 75 111 37 55 73 111 For each pair of latitude and longitude coordinates, compute the following value: ((latitude + longitude) * (latitude + longitude + 1) / 2) + latitude. This can require up to 51 bits of precision. (Javascript performs exact arithmetic with up to 53 bits of precision).
Value 429945724065327 17466 4315 17093 For each number, form a list of numbers by dividing the number by 32 repeatedly and recording each remainder. Stop when the quotient (not the remainder) reaches zero. If you start at zero, just record a zero.
For example, 17466 divided by 32 is 545 with a remainder of 26, so "26" is the first number. Divide 545 by 32 to get 17 with a remainder of 1 making "1" the second number. Divide 17 by 32 to get zero with a remainder of 17 making "17". the last and final number in the sequence.
15, 17, 21, 15, 2, 5, 2, 1, 7, 12 26, 1, 17 27, 6, 4 5, 22, 16Add 32 to each number except for the last number in each list.
47, 49, 53, 47, 34, 37, 34, 33, 39, 12 58, 33, 17 59, 38, 4 37, 54, 16Form a string by converting each number to a character using the following lookup table.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J K L M N O P 16 17 18 19 20 21 22 23 24 25 26 27 28 Q R S T U V W X Y Z a b c 29 30 31 32 33 34 35 36 37 38 39 40 41 d e f g h i j k l m n o p 42 43 44 45 46 47 48 49 50 51 52 53 54 q r s t u v w x y z 0 1 2 55 56 57 58 59 60 61 62 63 3 4 5 6 7 8 9 _ -vx1vilihnM 6hR 7mE l2QConcatenate the strings and use this string as the encoded value for the points parameter.
points=vx1vilihnM6hR7mEl2Q
JavaScript Implementation
The following JavaScript code is an implementation of this algorithm.
function encodePoints(points) {
var latitude = 0;
var longitude = 0;
var result = [];
var l;
for (var point in points ) {
// step 2
var newLatitude = Math.round(points[point][0] * 100000);
var newLongitude = Math.round(points[point][1] * 100000);
// step 3
var dy = newLatitude - latitude;
var dx = newLongitude - longitude;
latitude = newLatitude;
longitude = newLongitude;
// step 4 and 5
dy = (dy << 1) ^ (dy >> 31);
dx = (dx << 1) ^ (dx >> 31);
// step 6
var index = ((dy + dx) * (dy + dx + 1) / 2) + dy;
while (index > 0) {
// step 7
var rem = index & 31;
index = (index - rem) / 32;
// step 8
if (index > 0) rem += 32;
// step 9
result.push("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-"[rem]);
}
}
// step 10
return result.join("");
}
Testing Your Algorithm Implementation
The following URL is provided for you to test your algorithm. You can compare the compressed string computed by this URL for a small number of points to the compressed string computed by your implementation. There is no value in using this to create the compressed string in general because you are subject to the same length limitation as the Elevation API URLs.
http://dev.virtualearth.net/REST/v1/Elevation/PointCompression?points={lat1,long1,lat2,long2,latn,longn}&key={BingMapsKey}
Example: TEST Request
The following request provides a set of test points in the URL request, and the response returns a compressed string in the value (JSON) or Value (XML) field.
http://dev.virtualearth.net/REST/v1/Elevation/PointCompression?points=35.894309002906084,-110.72522000409663,35.893930979073048,-110.72577999904752,35.893744984641671,-110.72606003843248&key={BingMapsKey}
JSON TEST Response
{
"authenticationResultCode":"ValidCredentials",
"brandLogoUri":"http:\/\/dev.virtualearth.net\/Branding\/logo_powered_by.png",
"copyright":"Copyright © 2012 Microsoft and its suppliers. All rights reserved. This API cannot be accessed and the content and any results may not be used, reproduced or transmitted in any manner without express written permission from Microsoft Corporation.",
"resourceSets":[
{
"estimatedTotal":1,
"resources":[
{
"__type":"CompressedPointList:http:\/\/schemas.microsoft.com\/search\/local\/ws\/rest\/v1",
"value":"vx1vilihnM6hR7mEl2Q"
}
]
}
],
"statusCode":200,
"statusDescription":"OK",
"traceId":"31fbc5fa9724425487a63838d552ae0b"
}
XML Test Response
<Response xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns="http://schemas.microsoft.com/search/local/ws/rest/v1">
<Copyright>
Copyright © 2012 Microsoft and its suppliers. All rights reserved. This API cannot be accessed and the content and any results may not be used, reproduced or transmitted in any manner without express written permission from Microsoft Corporation.
</Copyright>
<BrandLogoUri>http://dev.virtualearth.net/Branding/logo_powered_by.png</BrandLogoUri>
<StatusCode>200</StatusCode>
<StatusDescription>OK</StatusDescription>
<AuthenticationResultCode>ValidCredentials</AuthenticationResultCode>
<TraceId>
84aafc1217a94048a396338e4cdaefdf
</TraceId>
<ResourceSets>
<ResourceSet>
<EstimatedTotal>1</EstimatedTotal>
<Resources>
<CompressedPointList>
<Value>vx1vilihnM6hR7mEl2Q</Value>
</CompressedPointList>
</Resources>
</ResourceSet>
</ResourceSets>
</Response>