# Convex hull

``````class Point(Number x, Number y) {
method to_s {
"(#{x}, #{y})"
}
}

func ccw (Point a, Point b, Point c) {
(b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)
}

func tangent (Point a, Point b) {
(b.x - a.x) / (b.y - a.y)
}

func graham_scan (*coords) {

## sort points by y, secondary sort on x
var sp = coords.map { |a|
Point(a...)
}.sort { |a,b|
(a.y <=> b.y) ||
(a.x <=> b.x)
}

# need at least 3 points to make a hull
if (sp.len < 3) {
return sp
}

# first point on hull is minimum y point
var h = [sp.shift]

# re-sort the points by angle, secondary on x
sp = sp.map_kv { |k,v|
Pair(k, [tangent(h[0], v), v.x])
}.sort { |a,b|
(b.value[0] <=> a.value[0]) ||
(a.value[1] <=> b.value[1])
}.map { |a|
sp[a.key]
}

# first point of re-sorted list is guaranteed to be on hull
h << sp.shift

# check through the remaining list making sure that
# there is always a positive angle
sp.each { |point|
loop {
if (ccw(h.last(2)..., point) >= 0) {
h << point
break
} else {
h.pop
}
}
}

return h
}

var hull = graham_scan(
[16, 3], [12,17], [ 0, 6], [-4,-6], [16, 6], [16,-7], [16,-3],
[17,-4], [ 5,19], [19,-8], [ 3,16], [12,13], [ 3,-4], [17, 5],
[-3,15], [-3,-9], [ 0,11], [-9,-3], [-4,-2], [12,10])

say("Convex Hull (#{hull.len} points): ", hull.join(" "))

hull = graham_scan(
[16, 3], [12,17], [ 0, 6], [-4,-6], [16, 6], [16,-7], [16,-3],
[17,-4], [ 5,19], [19,-8], [ 3,16], [12,13], [ 3,-4], [17, 5],
[-3,15], [-3,-9], [ 0,11], [-9,-3], [-4,-2], [12,10], [14,-9], [1,-9])

say("Convex Hull (#{hull.len} points): ", hull.join(" "))
``````

#### Output:

``````Convex Hull (7 points): (-3, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)
Convex Hull (9 points): (-3, -9) (1, -9) (14, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)
``````