EncodedPolyline.rb

# from http://blog.portable-eggplant.org/2007/02/13/ruby-polyline-encoder-for-google-maps/
class EncodedPolyline
  attr_reader :points, :encoded_points, :encoded_levels

  def initialize(points, culling_level = 0)
    @points = points
    points = []
    for point in @points
      points << Hash["lat" => point.y, "long" => point.x, "lev" => "unset"]
    end
    @encoded_levels, points = encode_levels(points, culling_level)
    @encoded_points = encode_points(points)
  end

  private

  def encode_points(points)
    encoded_points = ""
    plat = 0
    plng = 0
    for point in points
      lat = point["lat"]
      lng = point["long"]
      late5 = (lat.to_f * 1e5).floor
      lnge5 = (lng.to_f * 1e5).floor
      dlat = late5 - plat
      dlng = lnge5 - plng
      plat = late5
      plng = lnge5
      encoded_points << encode_signed_number(dlat) + encode_signed_number(dlng)
    end
    return encoded_points
  end

  def encode_levels(points, culling_level = 0)
    num_levels = 18
    len = points.length
    points[0]["lev"] = 17
    points[len-1]["lev"] = 17
    level = 17
    while level >= 0
      small = 500000*(2.0**(level-18))
      i = j = 1
      while i < len-1
        if dist(points[i], points[j]) >= small && points[i]["lev"] == "unset"
          points[i]["lev"] = level
          j = i
        end
        if points[i]["lev"] != "unset"
          j=i
        end
        i += 1
      end
      level -= 1
    end
    for point in points
      if point["lev"] == "unset"
        point["lev"] = 0
      end
    end
    encoded_levels = ""
    pared_points = []
    for point in points
      unless point["lev"] < culling_level
        pared_points << point
        encoded_levels << encode_number(point["lev"])
      end
    end
    return [encoded_levels, pared_points]
  end

  def encode_signed_number(num)
    sgn_num = num << 1
    if (num < 0)
      sgn_num = ~(sgn_num)
    end
    encode_number(sgn_num)
  end

  def encode_number(num)
    encode_string = ""
    while (num >= 0x20)
      next_value = (0x20 | (num & 0x1f)) + 63
      encode_string << next_value.chr if (next_value == 92)
      encode_string << next_value.chr
      num = num >> 5
    end
    final_value = num + 63
    encode_string << final_value.chr if (final_value == 92)
    encode_string << final_value.chr
    return encode_string
  end

  def dist(point1, point2)
    deg = 0.0174532925199
    12746004.5*Math.asin(Math.sqrt((Math.sin((point1["lat"].to_f - point2["lat"].to_f)*deg/2)**2) + Math.cos(point1["lat"].to_f*deg)*Math.cos(point2["lat"].to_f*deg)*(Math.sin((point1["long"].to_f - point2["long"].to_f)*deg/2)**2)))
  end

end