# vim: syntax=perl

use strict;
require "cgeom/utils";

# Graham's scan for convex hull
sub graham {
    my ($gr, %opts) = @_;
    my (@V, @HV, @HE, @AE, $low, $v, $es);
    # @V: all vertices
    @V = values %{ $gr->cget(-vertices) };
    $low = splice @V, pick_extreme(Vector2->new(0,-1), map { $_->pos() } @V), 1;
#    @V = sort { $low->pos()->orient2d($b->pos(), $a->pos()) } @V;
    # whichever of $a and $b has the smaller signed angle, should be
    # placed closer to the head.
    @V = sort { ($b->pos()-$low->pos())->signed_area($a->pos()-$low->pos()) } @V;
    # @AE: auxiliary edges
    @AE = map { Edge->new($low, $_, -status=>"discard") } @V;
    # @HV: hull vertices
    @HV = ($low, shift @V);
    # @HE: hull edges
    $HE[0] = Edge->new($HV[0], $HV[1], -status=>"done");
    foreach $v (@V, @HV) {
	$es = Edge->new($HV[$#HV], $v, -status=>"focus");
	$gr->cget(-canvas)->set_mark(0);
	while ( ( $HV[$#HV]->pos() - $HV[$#HV-1]->pos() )
	    -> signed_area( $v->pos() - $HV[$#HV-1]->pos() ) < 0 ) {
	    (pop @HE)->configure(-status=>"hidden");
	    pop @HV;
	    $es->set_ends($HV[$#HV], $v);
	    $gr->cget(-canvas)->set_mark(0);
	}
	push @HV, $v;
	push @HE, $es;
	$es->configure(-status=>"done");
	$gr->cget(-canvas)->set_mark(1);
    }
    map { $_->configure(-status=>"hidden") } @AE;
    $gr->cget(-canvas)->set_mark(1);
}

1;