convex_hull.rb

require 'minitest/autorun'

module ConvexHull
  class << self
    def find(points)
      sorted = points.sort.uniq
      reversed = sorted.reverse
      [sorted, reversed].map do |points|
        points.
          reduce([]) {|acc, p| add_to_convex_list p, acc }.
          values_at(0..-2)
      end.
      reduce(&:+)
    end

    # returns positive if angle between OA and OB is counter-clockwise
    private def perp_prod(o, a, b)
      ox, oy = o
      ax, ay = a
      bx, by = b
      (ax - ox) * (by - oy) - (ay - oy) * (bx - ox) 
    end

    private def add_to_convex_list(p, list)
      if list.size < 2
        list << p
      else
        if perp_prod(list[-2], list[-1], p) <= 0
          list.pop
          add_to_convex_list p, list
        else
          list << p
        end
      end
    end
  end
end


class TestConvexHull < MiniTest::Unit::TestCase
  def test_finding_hull_00_99
    points = (0..9).to_a.repeated_permutation(2)
    assert_equal(
      ConvexHull::find(points),
      [[0,0], [9,0], [9,9], [0,9]]
    )
  end
end