Convex hull: Difference between revisions

Line 1,913:

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~~. The original returned the correct answer for the task example, but only by accident. If the points (14,-9), (1,-9) were added to the task example, it wouldn't give a correct answer. Now it does~~.

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 ) >= 0 {

if ccw( |@h.tail(2), $point ) > 0 {

@h.push: $point;

} else {

@h.pop;

@h.push: $point and next if +@h < 2;

redo;

}

Line 1,974:

Line 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), (14,-9), (1,-9)

(-3,15), (-3,-9), ( 0,11), (-9,-3), (-4,-2), (12,10), (20,-9), (1,-9)

);

Line 1,980:

Line 1,981:

<pre>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)]

Convex Hull (7 points): [(-3, -9) (20, -9) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]</pre>

</pre>

=={{header|REXX}}==