#!/usr/bin/perl

# point_in_triangle( $x, $y, $x0, $y0, $x1, $y1, $x2, $y2 ) returns
# true if the point ($x,$y) is inside the triangle defined by
# the following points.

sub point_in_triangle {
    my ( $x, $y, $x0, $y0, $x1, $y1, $x2, $y2 ) = @_;

    # clockwise() from earlier in the chapter.
    my $cw0 = clockwise( $x0, $y0, $x1, $y1, $x, $y );
    return 1 if abs( $cw0 ) < epsilon; # On 1st edge.

    my $cw1 = clockwise( $x1, $y1, $x2, $y2, $x, $y );
    return 1 if abs( $cw1 ) < epsilon; # On 2nd edge.

    # Fail if the sign changed.
    return 0 if ( $cw0 < 0 and $cw1 > 0 ) or ( $cw0 > 0 and $cw1 < 0 );

    my $cw2 = clockwise( $x2, $y2, $x0, $y0, $x, $y );
    return 1 if abs( $cw2 ) < epsilon; # On 3rd edge.

    # Fail if the sign changed.
    return 0 if ( $cw0 < 0 and $cw2 > 0 ) or ( $cw0 > 0 and $cw2 < 0 );

    # Jubilate!
    return 1;
}

@triangle = ( 1, 1,  5, 6,  9, 3 );
print "(1, 1): ", point_in_triangle( 1, 1,  @triangle ), "\n";
print "(1, 2): ", point_in_triangle( 1, 2,  @triangle ), "\n";
print "(3, 2): ", point_in_triangle( 3, 2,  @triangle ), "\n";
print "(3, 3): ", point_in_triangle( 3, 3,  @triangle ), "\n";
print "(3, 4): ", point_in_triangle( 3, 4,  @triangle ), "\n";
print "(5, 1): ", point_in_triangle( 5, 1,  @triangle ), "\n";
print "(5, 2): ", point_in_triangle( 5, 2,  @triangle ), "\n";

# clockwise( $x0, $y0, $x1, $y1, $x2, $y2 )
#    Return positive if one must turn clockwise (right) when moving
#    from p0 (x0, y0) to p1 to p2, negative if counterclockwise (left).
#    It returns zero if the three points lie on the same line --
#    but beware of floating point errors.
#
sub clockwise {
    my ( $x0, $y0, $x1, $y1, $x2, $y2 ) = @_;
    return ( $x2 - $x0 ) * ( $y1 - $y0 ) - ( $x1 - $x0 ) * ( $y2 - $y0 );
}