File: graham

package info (click to toggle)
algotutor 0.8.6-4
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, sid
  • size: 576 kB
  • sloc: perl: 2,563; makefile: 41; php: 24; sh: 1
file content (43 lines) | stat: -rw-r--r-- 1,349 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 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;