Given a point and radius, generate a polygonal circle

circle_processor.rb

# This class converts a point and a given radius into a polygonal circle.
# The error_distance is a parameter to the number of sides the polygon will have.
# The lower the number, the more sides it will have, and the more accurate the circle.
class CircleProcessor
  TO_RADIANS = Math::PI / 180.0
  MIN_NUM_SIDES = 4
  MAX_NUM_SIDES = 1000
  TO_METERS = 6_371_008.7714 # Earth's mean radius in meters.

  def initialize(error_distance)
    @error_distance = error_distance
  end

  # Convert a point and radius into the coordinates of a circular polygon.
  #
  # This is accomplished by dividing the circle into _n_ angles and moving along that angle until it is
  # _radius_ away from the center.
  #
  # @param [Array<Float>] coords Array of latitude and longitude
  # @param [Float, Integer] radius
  # @return [Array<Array<Float>>] An array of coordinates in longitude/latitude order
  def create_polygon(coords, radius)
    sides = num_sides(radius)
    result = [[], []]
    sides.times do |i|
      factor = 2.0
      step = 1.0
      last = 0
      # The angle in degrees the point is for.
      angle_d = (i * (360.0 / sides)) * TO_RADIANS
      x = Math.cos(angle_d)
      y = Math.sin(angle_d)
      # Move a point along the angle from center until it's distance from center is close to `radius`.
      loop do
        lat = coords[0] + y * factor
        lon = coords[1] + x * factor
        distance_meters = haversine_distance(coords[0], coords[1], lat, lon)

        if (distance_meters - radius).abs < 0.1
          result[0][i] = lon
          result[1][i] = lat
          break
        end

        if distance_meters > radius
          factor -= step
          step /= 2.0 if last == 1
          last = -1
        elsif distance_meters < radius
          factor += step
          step /= 2.0 if last == -1
          last = 1
        end
      end
    end
    # Close the polygon
    result[0][sides] = result[0][0]
    result[1][sides] = result[1][0]
    result[0].zip(result[1])
  end

  private

  # Calculate the number of sides the polygon needs for the given radius and error distance.
  #
  # @param [Float, Integer] radius
  # @return [Integer]
  def num_sides(radius)
    val = (2 * Math::PI / Math.acos(1 - @error_distance / radius.to_f)).ceil
    if val > MAX_NUM_SIDES
      MAX_NUM_SIDES
    elsif val < MIN_NUM_SIDES
      MIN_NUM_SIDES
    else
      val.to_i
    end
  rescue Math::DomainError
    MIN_NUM_SIDES
  end

  # Calculate the haversine distance in meters.
  #
  # @param [Float] lat1
  # @param [Float] lon1
  # @param [Float] lat2
  # @param [Float] lon2
  # @return [Float]
  def haversine_distance(lat1, lon1, lat2, lon2)
    # Calculate radial arcs for latitude and longitude
    d_lat = (lat2 - lat1) * TO_RADIANS
    d_lon = (lon2 - lon1) * TO_RADIANS

    a = Math.sin(d_lat / 2)**2 + Math.cos(lat1 * TO_RADIANS) * Math.cos(lat2 * TO_RADIANS) * Math.sin(d_lon / 2)**2
    c = 2.0 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a))
    # Convert to meters
    c * TO_METERS
  end
end