File Coverage

lib/Math/ConvexHull.pm

Criterion	Covered	Total	%
statement	66	68	97.0
branch	9	12	75.0
condition	14	18	77.7
subroutine	8	8	100.0
pod	1	1	100.0
total	98	107	91.5

package Math::ConvexHull;
use 5.006;
use strict;
use warnings;

use constant PI => 3.1415926535897932384626433832795;

require Exporter;

our $VERSION = '1.04';


our @ISA = qw(Exporter);

our @EXPORT_OK = qw(
        convex_hull
);

our %EXPORT_TAGS = ( 'all' => \@EXPORT_OK );


sub convex_hull {
        my $points = shift;

        my $start_index = _find_start_point($points); # O(n)

        my $angles_points = _calculate_angles($points, $start_index); # O(n)
        my $start = splice(@$angles_points, $start_index, 1);

        @$angles_points =
                        sort {
                                $a->[0] <=> $b->[0] ||
                                $a->[1][0] <=> $b->[1][0] ||
                                $a->[1][1] <=> $b->[1][1]
                        }
                        @$angles_points;             # O(n*log(n))

        unshift @$angles_points, $start;

        # remove duplicates (O(n))
        # At the same time, drop the angle
        my $prev = $angles_points->[0][1];
        my @hull;
        push @hull, $prev;
        for my $r (@$angles_points) {
                my $p = $r->[1];
                push @hull, $p
                        if (   $p->[0]+1e-15 <= $prev->[0] || $p->[0]-1e-15 >= $prev->[0]
                            || $p->[1]+1e-15 <= $prev->[1] || $p->[1]-1e-15 >= $prev->[1]);
                $prev = $p;
        }

        # copy of the reference point as sentinel to stop loop
        unshift @hull, $hull[0];

        my $n_in_hull = 2;
        # O(n)
        for (my $i = 3; $i < @hull; ++$i) {
                while (
                        _ccw(
                                $hull[$n_in_hull-1],
                                $hull[$n_in_hull],
                                $hull[$i]
                        ) <= 0
                ) {
                        if ($n_in_hull == 2) {
                                ($hull[$i], $hull[$n_in_hull]) = (@hull[$n_in_hull, $i]);
                                ++$i;
                        }
                        else {
                                --$n_in_hull;
                        }
                }
                ++$n_in_hull;
                ($hull[$i], $hull[$n_in_hull]) = (@hull[$n_in_hull, $i]);
        }

        # return points in hull
        return [@hull[1..$n_in_hull]];
}

sub _ccw {
        my $p1 = shift;
        my $p2 = shift;
        my $p3 = shift;

        return(
                ($p2->[0] - $p1->[0])*($p3->[1] - $p1->[1])
                -
                ($p2->[1] - $p1->[1])*($p3->[0] - $p1->[0])
        );
}

sub _calculate_angles {
        my $points = shift;
        my $start  = shift;

        my $s_x = $points->[$start]->[0];
        my $s_y = $points->[$start]->[1];

        my $angles = [];

        my $p_no = 0;
        foreach my $p (@$points) {
                my $angle;
                if ($p_no == $start) {
                        $angle = 0;
                }
                else {
                        my $x_diff = $p->[0] - $s_x;
                        my $y_diff = $p->[1] - $s_y;

                        $angle = atan2($y_diff, $x_diff);
                        $angle = PI-$angle if $angle < 0;
                }

                push @$angles, [$angle, $p];
                $p_no++;
        }

        return $angles;
}



# Returns the index of the starting point.
sub _find_start_point {
        my $points = shift;

        # Looking for the lowest, then leftmost point.

        my $s_point = 0;

        for (my $i = 1; $i < @$points; $i++) {
                my ($p0, $p1)   = @{ $points->[$i] };
                my ($sp0, $sp1) = @{ $points->[$s_point] };
                if (
                        $p1 <= $sp1 and
                        $p1 < $sp1 ||
                        $p0 < $sp0
                ) {
                        $s_point = $i;
                }
        }

        return $s_point;
}



1;
__END__