1Math::ConvexHull::MonotUosneerChCaoinnt(r3i)buted Perl DMoactuhm:e:nCtoantvieoxnHull::MonotoneChain(3)
2
3
4

NAME

6       Math::ConvexHull::MonotoneChain - Andrew's monotone chain algorithm for
7       finding a convex hull in 2D
8

SYNOPSIS

10         use Math::ConvexHull::MonotoneChain 'convex_hull';
11         my $ch = convex_hull(
12           [
13             [0, 0],
14             [0, 1],
15             [1, 0],
16             [0.5, 0.5],
17             [1, 1],
18           ]
19         );
20
21         # $ch is now:
22         # [ [0, 0],
23         #   [1, 0],
24         #   [1, 1],
25         #   [0, 1], ]
26

DESCRIPTION

28       This is somewhat experimental still.
29
30       This (XS) module optionally exports a single function "convex_hull"
31       which calculates the convex hull of the input points and returns it.
32       The algorithm is "O(n log n)" due to having to sort the input list, but
33       should be somewhat faster than a plain Graham's scan (also "O(n log
34       n)") in practice since it avoids polar coordinates.
35

FUNCTIONS

37   convex_hull
38       Expects an array ref of points as input, returns an array ref of of the
39       points in the convex hull, ordered counter-clockwise.
40
41       point refers to an array reference containing an X, and a Y coordinate.
42
43       For less than three input points, this will return an array reference
44       whose elements are the input points (without cloning).
45

SEE ALSO

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

AUTHOR

50       Steffen Mueller, <smueller@cpan.org>
51

53       Copyright (C) 2011 by Steffen Mueller
54
55       This library is free software; you can redistribute it and/or modify it
56       under the same terms as Perl itself, either Perl version 5.8.0 or, at
57       your option, any later version of Perl 5 you may have available.
58
59
60
61perl v5.28.1                      2011-11-09Math::ConvexHull::MonotoneChain(3)
Impressum