Convex hull: Difference between revisions
Content added Content deleted
m (C - removed unnecessary casts) |
Thundergnat (talk | contribs) m (→{{header|Raku}}: Modify to ignore colinear points, trap edge condition, update output) |
||
Line 1,913:
{{works with|Rakudo|2017.05}}
{{trans|zkl}}
Modified the angle sort method as the original could fail if there were multiple points on the same y coordinate as the starting point. Sorts on tangent rather than triangle area. Inexpensive since it still doesn't do any trigonometric math, just calculates the ratio of opposite over adjacent
<lang perl6>class Point {
Line 1,953:
# there is always a positive angle
for @sp -> $point {
if ccw( |@h.tail(2), $point ) >
@h.push: $point;
} else {
@h.pop;
@h.push: $point and next if +@h < 2;
redo;
}
Line 1,974 ⟶ 1,975:
(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), (
);
Line 1,980 ⟶ 1,981:
{{out}}
<pre>Convex Hull (7 points): [(-3, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]
Convex Hull (
=={{header|REXX}}==
|