rdp.rb

module RamerDouglasPeucker
      def self.perpendicular_distance(p1, p2, p3)
        # Measures the shortest distance of p3 from a line drawn between p1 and p2
        # https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
        numerator = (
          p3[0] * (p2[1] - p1[1]) -
          p3[1] * (p2[0] - p1[0]) +
          p2[0] * p1[1] - p2[1] * p1[0]
        ).abs

        denominator = (
          (p2[1] - p1[1])**2 + (p2[0] - p1[0])**2
        )**(0.5)

        numerator / denominator
      end

      def self.ramer_douglas_peucker(point_array, minimum_feature)
        end_index = point_array.count - 1
        if point_array[0] == point_array[end_index] && point_array.count > 2
          end_index = point_array.count - 2
        end

        max_point = (1...end_index).inject([0, 0]) do |current_max, index|
          current_point    = point_array[index]
          current_distance = perpendicular_distance(
            point_array[0],
            point_array[end_index],
            current_point
          )

          current_max = if current_distance > current_max[1]
                          [index, current_distance]
                        else
                          current_max
                        end

          current_max
        end

        if max_point[1] > minimum_feature
          left_side  = ramer_douglas_peucker point_array[0...max_point[0]],
                                             minimum_feature

          right_side = ramer_douglas_peucker point_array[max_point[0]..end_index],
                                             minimum_feature

          results = left_side + right_side
        else
          results = [point_array[0], point_array[end_index]]
        end

        results
      end
end