[Gllug] Algorithm question

[Adrian McMenamin]

Slighty off-topic but FWIW: the perl module I used
Math::NumberCruncher::InPolygon - is buggy as it fails on (some of) the
boundary conditions - correctly identifies (0, 0, 0) as in the (0, 0, 0)
(255, 255, 255) polygon, but fails when either x, y or z are 255.

Here is the code - I intend to sit down and work out what is wrong with it
this evening, but if any guru can spot it now that would be great:

sub InPolygon {
    shift if UNIVERSAL::isa( $_[ 0 ], __PACKAGE__ );
    my ( $x, $y, @xy ) = @_;
    return undef unless defined $x && defined $y && @xy > 0;
    my $n = @xy / 2;
    my @i = map { 2 * $_ } 0 .. ( @xy / 2 );
    my @x = map { $xy[ $_ ] } @i;
    my @y = map { $xy[ $_ + 1 ] } @i;
    my ( $i, $j );
    my $side = 0;

    for ( $i = 0, $j = $n - 1 ; $i < $n ; $j = $i++ ) {
        if ( ( ( ( $y[ $i ] <= $y ) && ( $y < $y[ $j ] ) ) || ( ( $y[ $j ]
<= $y ) && ( $y < $y[ $i ] ) ) )
            and ( $x < ( $x[ $j ] - $x[ $i ] ) * ( $y - $y[ $i ] ) / ( $y[
$j ] - $y[ $i ] ) + $x[ $i ] ) )
        {
            $side = not $side;
        }
    }
    return $side ? 1 : 0;
}



-------------- next part --------------
-- 
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug