Steffen Müller >
Math-ConvexHull-MonotoneChain >
Math::ConvexHull::MonotoneChain

Module Version: 0.01
Math::ConvexHull::MonotoneChain - Andrew's monotone chain algorithm for finding a convex hull in 2D

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], ]

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.

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).

Math::ConvexHull, which uses Graham's scan in pure Perl.

Steffen Mueller, <smueller@cpan.org>

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.

syntax highlighting: