branch14.org

 1 module ConvexHull
       2 
       3   # after graham & andrew
       4   def self.calculate(points)
       5     lop = points.sort_by { |p| p.x }
       6     left = lop.shift
       7     right = lop.pop
       8     lower, upper = [left], [left]
       9     lower_hull, upper_hull = [], []
      10     det_func = determinant_function(left, right)
      11     until lop.empty?
      12       p = lop.shift
      13       ( det_func.call(p) < 0 ? lower : upper ) << p
      14     end
      15     lower << right
      16     until lower.empty?
      17       lower_hull << lower.shift
      18       while (lower_hull.size >= 3) &&
      19           !convex?(lower_hull.last(3), true)
      20         last = lower_hull.pop
      21         lower_hull.pop
      22         lower_hull << last
      23       end
      24     end
      25     upper << right
      26     until upper.empty?
      27       upper_hull << upper.shift
      28       while (upper_hull.size >= 3) &&
      29           !convex?(upper_hull.last(3), false)
      30         last = upper_hull.pop
      31         upper_hull.pop
      32         upper_hull << last
      33       end
      34     end
      35     upper_hull.shift
      36     upper_hull.pop
      37     lower_hull + upper_hull.reverse
      38   end
      39   
      40   private
      41 
      42   def self.determinant_function(p0, p1)
      43     proc { |p| ((p0.x-p1.x)*(p.y-p1.y))-((p.x-p1.x)*(p0.y-p1.y)) }
      44   end
      45   
      46   def self.convex?(list_of_three, lower)
      47     p0, p1, p2 = list_of_three
      48     (determinant_function(p0, p2).call(p1) > 0) ^ lower
      49   end
      50   
      51 end