Andrew's monotone chain convex hull algorithm

monotone_chain_convex_hull.rb

# Andrew's monotone chain convex hull algorithm constructs the convex hull 
# of a set of 2-dimensional points in O(n\log n) time.

# It does so by first sorting the points lexicographically (first by x-coordinate, 
# and in case of a tie, by y-coordinate), and then constructing upper and lower 
# hulls of the points inO(n) time.

# An upper hull is the part of the convex hull, which is visible from the above. 
# It runs from its rightmost point to the leftmost point in counterclockwise order. 
# Lower hull is the remaining part of the convex hull.

class ConvexHull
  def initialize(points)
    @points = points.sort.uniq
  end
  
  def solve
    return @points if @points.size <= 3
    lower = monotone_chain @points
    upper = monotone_chain @points.reverse
    lower + upper
  end
  
  def monotone_chain(points)
    chain = []
    points.each do |p|
      chain.pop while chain.size > 1 and cross(chain[-2], chain[-1], p) <= 0
      chain.push p
    end
    chain[0...-1]  
  end
  
  def cross(o, a, b)
    (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
  end
end

convex_hull = ConvexHull.new (0..9).to_a.repeated_permutation(2).to_a  
fail unless convex_hull.solve == [[0, 0], [9, 0], [9, 9], [0, 9]]