74 lines
1.8 KiB
Text
74 lines
1.8 KiB
Text
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(" "))
|