NAME¶
Math::ConvexHull::MonotoneChain - Andrew's monotone chain algorithm for finding
a convex hull in 2D
SYNOPSIS¶
use Math::ConvexHull::MonotoneChain 'convex_hull';
my $ch = convex_hull(
[
[0, 0],
[0, 1],
[1, 0],
[0.5, 0.5],
[1, 1],
]
);
# $ch is now:
# [ [0, 0],
# [1, 0],
# [1, 1],
# [0, 1], ]
DESCRIPTION¶
This is somewhat experimental still.
This (XS) module optionally exports a single function "convex_hull"
which calculates the convex hull of the input points and returns it. The
algorithm is "O(n log n)" due to having to sort the input list, but
should be somewhat faster than a plain Graham's scan (also "O(n log
n)") in practice since it avoids polar coordinates.
FUNCTIONS¶
convex_hull¶
Expects an array ref of points as input, returns an array ref of of the points
in the convex hull, ordered counter-clockwise.
point refers to an array reference containing an X, and a Y coordinate.
For less than three input points, this will return an array reference whose
elements are the input points (without cloning).
SEE ALSO¶
Math::ConvexHull, which uses Graham's scan in pure Perl.
AUTHOR¶
Steffen Mueller, <smueller@cpan.org>
COPYRIGHT AND LICENSE¶
Copyright (C) 2011 by Steffen Mueller
This library is free software; you can redistribute it and/or modify it under
the same terms as Perl itself, either Perl version 5.8.0 or, at your option,
any later version of Perl 5 you may have available.