package Math::ConvexHull::MonotoneChain;
use 5.008001;
use strict;
use warnings;
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT_OK = qw(
convex_hull
);
our @EXPORT = qw();
our %EXPORT_TAGS = ('all' => \@EXPORT_OK);
our $VERSION = '0.01';
require XSLoader;
XSLoader::load('Math::ConvexHull::MonotoneChain', $VERSION);
sub convex_hull {
my $ary_ref = shift;
return convex_hull_sorted([
sort {$a->[0] <=> $b->[0] || $a->[1] <=> $b->[1]} @$ary_ref
]);
}
1;
__END__
=head1 NAME
Math::ConvexHull::MonotoneChain - Andrew's monotone chain algorithm for finding a convex hull in 2D
=head1 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], ]
=head1 DESCRIPTION
This is somewhat experimental still.
This (XS) module optionally exports a single function C
which calculates the convex hull of the input points and returns it.
The algorithm is C due to having to sort the input list,
but should be somewhat faster than a plain Graham's scan (also C)
in practice since it avoids polar coordinates.
=head1 FUNCTIONS
=head2 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.
I 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).
=head1 SEE ALSO
L, which uses Graham's scan in pure Perl.
=head1 AUTHOR
Steffen Mueller, Esmueller@cpan.orgE
=head1 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.
=cut