Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C# implementation of Google's 'Encoded Polyline Algorithm'

Does anyone have a concise and robust implementation of Google's Encoded Polyline Algorithm in C#?

I essentially want the implementation of this signature:

public string Encode(IEnumerable<Point> points); 
like image 677
Drew Noakes Avatar asked Oct 04 '10 01:10

Drew Noakes


2 Answers

Here's the implementation I settled on:

public static string Encode(IEnumerable<GeoLocation> points) {     var str = new StringBuilder();      var encodeDiff = (Action<int>)(diff => {         int shifted = diff << 1;         if (diff < 0)             shifted = ~shifted;         int rem = shifted;         while (rem >= 0x20)         {             str.Append((char)((0x20 | (rem & 0x1f)) + 63));             rem >>= 5;         }         str.Append((char)(rem + 63));     });      int lastLat = 0;     int lastLng = 0;     foreach (var point in points)     {         int lat = (int)Math.Round(point.Latitude * 1E5);         int lng = (int)Math.Round(point.Longitude * 1E5);         encodeDiff(lat - lastLat);         encodeDiff(lng - lastLng);         lastLat = lat;         lastLng = lng;     }     return str.ToString(); } 

Hope that helps someone else out.

like image 169
Drew Noakes Avatar answered Sep 19 '22 02:09

Drew Noakes


Maybe is late but I've just solved the same problem but to Encode list of locations and Decode polylines, I used http://json2csharp.com/ to generate corresponding classes in C# in order to deserialize the response with JsonConvert like:

  var googleDirectionsResponse = JsonConvert.DeserializeObject<RootObject>(responseString); 

This gave me this definition of Location (I'll clean it sooner or later):

public class Location {     public double lat { get; set; }     public double lng { get; set; } } 

And I created a converter class to do the trick in both directions (IT's not original, it is just a refactor from this class: https://gist.github.com/shinyzhu/4617989 ):

/// <summary> /// Google Polyline Converter (Encoder and Decoder) /// </summary> public static class GooglePolylineConverter {     /// <summary>     /// Decodes the specified polyline string.     /// </summary>     /// <param name="polylineString">The polyline string.</param>     /// <returns>A list with Locations</returns>     public static IEnumerable<Location> Decode(string polylineString)     {         if (string.IsNullOrEmpty(polylineString))             throw new ArgumentNullException(nameof(polylineString));          var polylineChars = polylineString.ToCharArray();         var index = 0;          var currentLat = 0;         var currentLng = 0;          while (index < polylineChars.Length)         {             // Next lat             var sum = 0;             var shifter = 0;             int nextFiveBits;             do             {                 nextFiveBits = polylineChars[index++] - 63;                 sum |= (nextFiveBits & 31) << shifter;                 shifter += 5;             } while (nextFiveBits >= 32 && index < polylineChars.Length);              if (index >= polylineChars.Length)                 break;              currentLat += (sum & 1) == 1 ? ~(sum >> 1) : (sum >> 1);              // Next lng             sum = 0;             shifter = 0;             do             {                 nextFiveBits = polylineChars[index++] - 63;                 sum |= (nextFiveBits & 31) << shifter;                 shifter += 5;             } while (nextFiveBits >= 32 && index < polylineChars.Length);              if (index >= polylineChars.Length && nextFiveBits >= 32)                 break;              currentLng += (sum & 1) == 1 ? ~(sum >> 1) : (sum >> 1);              yield return new Location             {                 lat = Convert.ToDouble(currentLat) / 1E5,                 lng = Convert.ToDouble(currentLng) / 1E5             };         }     }      /// <summary>     /// Encodes the specified locations list.     /// </summary>     /// <param name="locations">The locations.</param>     /// <returns>The polyline string.</returns>     public static string Encode(IEnumerable<Location> locations)     {         var str = new StringBuilder();          var encodeDiff = (Action<int>)(diff =>         {             var shifted = diff << 1;             if (diff < 0)                 shifted = ~shifted;              var rem = shifted;              while (rem >= 0x20)             {                 str.Append((char)((0x20 | (rem & 0x1f)) + 63));                  rem >>= 5;             }              str.Append((char)(rem + 63));         });          var lastLat = 0;         var lastLng = 0;          foreach (var point in locations)         {             var lat = (int)Math.Round(point.lat * 1E5);             var lng = (int)Math.Round(point.lng * 1E5);              encodeDiff(lat - lastLat);             encodeDiff(lng - lastLng);              lastLat = lat;             lastLng = lng;         }          return str.ToString();     } } 

I hope it helps.

like image 24
Juan Avatar answered Sep 22 '22 02:09

Juan