Skip to content

Instantly share code, notes, and snippets.

@NaN1488
Last active December 20, 2015 19:08
Show Gist options
  • Save NaN1488/6180632 to your computer and use it in GitHub Desktop.
Save NaN1488/6180632 to your computer and use it in GitHub Desktop.
OpenStruct points to get the convex points list
module ConvexHull
def self.calculate(points)
lop = points.sort_by { |p| p.x }
left = lop.shift
right = lop.pop
lower, upper = [left], [left]
lower_hull, upper_hull = [], []
det_func = determinant_function(left, right)
until lop.empty?
p = lop.shift
( det_func.call(p) < 0 ? lower : upper ) << p
end
lower << right
until lower.empty?
lower_hull << lower.shift
while (lower_hull.size >= 3) &&
!convex?(lower_hull.last(3), true)
last = lower_hull.pop
lower_hull.pop
lower_hull << last
end
end
upper << right
until upper.empty?
upper_hull << upper.shift
while (upper_hull.size >= 3) &&
!convex?(upper_hull.last(3), false)
last = upper_hull.pop
upper_hull.pop
upper_hull << last
end
end
upper_hull.shift
upper_hull.pop
lower_hull + upper_hull.reverse
end
private
def self.determinant_function(p0, p1)
proc { |p| ((p0.x-p1.x)*(p.y-p1.y))-((p.x-p1.x)*(p0.y-p1.y)) }
end
def self.convex?(list_of_three, lower)
p0, p1, p2 = list_of_three
(determinant_function(p0, p2).call(p1) > 0) ^ lower
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment