# Point Compression Algorithm

Bing

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.

1. Start with a set of latitude and longitude values.

```35.894309002906084, -110.72522000409663
35.893930979073048, -110.72577999904752
35.893744984641671, -110.72606003843248
35.893366960808635, -110.72661500424147

```
2. Multiply each value by 100000 and round each result to the nearest integer.

```3589431, -11072522
3589393, -11072578
3589374, -11072606
3589337, -11072662

```
3. 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.

```
3589431, -11072522
-38,       -56
-19,       -28
-37,       -56

```
4. Multiply each value by 2.

```7178862, -22145044
-76,      -112
-38,       -56
-74,      -112

```
5. If any value is negative, change it to be a positive value, and then subtract 1.

```7178862,  22145043
75,       111
37,        55
73,       111

```
6. 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).

```429945724065327
17466
4315
17093

```
7. 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, 16
```
8. Add 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, 16
```
9. Form 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
l2Q

```
10. Concatenate 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 © 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.
<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>

```
Show: