oracular (3) Math::ConvexHull::MonotoneChain.3pm.gz

Provided by: libmath-convexhull-monotonechain-perl_0.1-2build4_amd64 bug

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