#!/usr/bin/perl

# convex_hull_graham( @xy )
#   Compute the convex hull of the points @xy using the Graham's scan.
#   Returns the convex hull points as a list of ($x,$y,...).

sub convex_hull_graham {
    my ( @xy ) = @_;

    my $n = @xy / 2;
    my @i = map { 2 * $_ } 0 .. ( $#xy / 2 ); # The even indices.
    my @x = map { $xy[ $_ ]     } @i;
    my @y = map { $xy[ $_ + 1 ] } @i;

    # First find the smallest y that has the smallest x.

    # $ymin is the smallest y so far, @xmini holds the indices
    # of the smallest y(s) so far, $xmini will the index of the
    # smallest x, $xmin the smallest x.
    my ( $ymin, $xmini, $xmin, $i );

    for ( $ymin = $ymax = $y[ 0 ], $i = 1; $i < $n; $i++ ) {
        if ( $y[ $i ] + epsilon < $ymin ) {
            $ymin  = $y[ $i ];
            @xmini = ( $i );
        } elsif ( abs( $y[ $i ] - $ymin ) < epsilon ) {
            $xmini = $i # Remember the index of the smallest x.
                if not defined $xmini or $x[ $i ] < $xmini;
        }
    }

    $xmin  = $x[ $xmini ];
    splice @x, $xmini, 1;         # Remove the minimum point.
    splice @y, $xmini, 1;

    my @a = map {  # Sort the points according to angle with that point.
                   atan2( $y[ $_ ] - $ymin,
                          $x[ $_ ] - $xmin)
                } 0 .. $#x;

    # An unusual Schwartzian Transform.  This leaves us the sorted
    # indices so that we can apply the sort multiple times -- a permutation.

    my @j = map { $_->[ 0 ] }
                sort {      # Sort by the angles, then by x, then by y.
                      return $a->[ 1 ] <=> $b->[ 1 ]             ||
                             $x[ $a->[ 0 ] ] <=> $x[ $b->[ 0 ] ] ||
                             $y[ $a->[ 0 ] ] <=> $y[ $b->[ 0 ] ];
                      }
                     map { [ $_, $a[ $_ ] ] } 0 .. $#a;

    @x = @x[ @j ];          # Permute.
    @y = @y[ @j ];
    @a = @a[ @j ];

    unshift @x, $xmin;      # Put back the minimum point.
    unshift @y, $ymin;
    unshift @a, 0;

    my @h = ( 0, 1 );        # The hull.
    my $cw;

  # Backtrack: while there are right turns or no turns, shrink the hull.
    for ( $i = 2; $i < $n; $i++ ) {
        while (
            clockwise( $x[ $h[ $#h - 1 ] ],
                       $y[ $h[ $#h - 1 ] ],
                       $x[ $h[ $#h ] ],
                       $y[ $h[ $#h ] ],
                       $x[ $i ],
                       $y[ $i ] ) < epsilon
               and @h >= 2 ) {  # Keep two points in hull at all times.
            pop @h;
        }
        push @h, $i;  # Grow the hull.
    }

    # Interlace x's and y's of the hull back into one list, and return.
    return map { ( $x[ $_ ], $y[ $_ ] ) } 0 .. $#h;
}