---
name: "Math::ConvexHull::MonotoneChain"
section: "3pm"
platform: "linux"
package: "libmath-convexhull-monotonechain-perl"
version: "0.1-2+b4"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Math::ConvexHull::MonotoneChain"
---

# Math::ConvexHull::MonotoneChain(3pm)

Andrew's monotone chain algorithm for finding a convex hull in 2D

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