p2-moritz

Download the raw code.

use v6;

sub parse-line($str) {
    $str.split(/\s+/).map: { [ .split(',')>>.Rat ]; }
}

sub is-point-in-polygon($point, @poly) {
    # count intersections between a vertical line from
    # -Inf to $point and the lines in @poly.
    # iff the count is odd, the point is inside the polygon.

    my ($x, $y) = $point.flat;
    sub vertical-intersection(@p1, @p2) {
        my @x = (@p1[0], @p2[0]).sort;
        my @y = (@p1[1], @p2[1]).sort;

        if @x[0] >= $x || @x[1] < $x || @y[0] > $y {
            # the line ($p1 -> $p2) is completely right, left or above the
            # point, so it can't intersect with our virtual vertical line
            return 0;
        }
        if all(@x) == $x {
            # a vertical line below or overlapping the point
            return @y[1] >= $y ?? 1 !! 0;
        }
        return 1 if @y[1] < $y;

        my $slope = (@p2[1] - @p1[1]) / (@p2[0] - @p1[0]);
        my $y-axis-intercept = $slope * ($x - @p1[0]) + @p1[1];
        return ($y-axis-intercept < $y).Int;
    }

    my $intersections = 0;
    for @poly Z @poly.rotate -> $p1, $p2 {
        $intersections += vertical-intersection($p1, $p2);
    }
    return so $intersections % 2;
}

multi MAIN() {
    my @poly-points = parse-line(get);
    my $test-point  = parse-line(get).[0];
    if $test-point ~~ Array && @poly-points > 1 {
        say is-point-in-polygon($test-point, @poly-points) ?? 'yes' !! 'no';
    } else {
        say "invalid input";
    }
}

multi MAIN('test') {
    use Test;
    plan *;

    my @points =  parse-line('1.0,1.0 1.0,-1.0 -1.0,-1.0 -1.0,1.0');
    ok  is-point-in-polygon([0,  0], @points), 'masaks example';
    nok is-point-in-polygon([0,  2], @points), 'masaks example with (0, 2)';
    nok is-point-in-polygon([2,  0], @points), 'masaks example with (2, 0)';
    nok is-point-in-polygon([0, -2], @points), 'masaks example with (0, -2)';
    nok is-point-in-polygon([-2, 0], @points), 'masaks example with (-2, 0)';
    nok is-point-in-polygon([1, -2], @points), 'masaks example with (1, -2)';
    nok is-point-in-polygon([1,  2], @points), 'masaks example with (1,  2)';
    nok is-point-in-polygon([-2, 1], @points), 'masaks example with (-2, 1)';

    # triangle
    #   (0,2)  +------+ (1, 2)
    #          |     /
    #          |   /
    #          |  /
    #          |/
    #   (0, 0) +

    my @triangle = parse-line('0.0,0.0 0.0,2.0 1.0,2.0');
    ok  is-point-in-polygon([0.5, 1.1], @triangle), 'triangle (+)';
    nok is-point-in-polygon([0.5, 0.9], @triangle), 'triangle (-)';
    @triangle.=reverse;
    ok  is-point-in-polygon([0.5, 1.1], @triangle), 'triangle (+, rot)';
    nok is-point-in-polygon([0.5, 0.9], @triangle), 'triangle (-, rot)';

    # also try a triangle with a negative slope
    #   (1, 3)   +
    #            | \
    #            |  \
    #            |   \
    #            |    \
    #   (1, 1)   +-----+  (2, 1)
    @triangle = parse-line('1.0,1.0 1.0,3.0 2.0,1.0');
    nok is-point-in-polygon([1.5, 2.1], @triangle), 'triangle (+)';
    ok  is-point-in-polygon([1.5, 1.9], @triangle), 'triangle (-)';
    @triangle.=reverse;
    nok is-point-in-polygon([1.5, 2.1], @triangle), 'triangle (+)';
    ok  is-point-in-polygon([1.5, 1.9], @triangle), 'triangle (-)';

    # non-convex shapes
    #   (0,2)  +-------+ (2, 2)
    #          |     /
    #          |    /
    #          |   /
    #          |  /
    #   (0, 0) |  +  (0, 1)
    #          |  \
    #          |   \
    #          |    \
    #          |     \
    #  (0, -2) +------+  (2, -2)

    my @nc = parse-line('0.0,-2.0 0.0,2.0 2.0,2.0 0.0,1.0 2.0,-2.0');
    ok  is-point-in-polygon([1.5, -1.3], @nc),
                'lower half of non-convex polygon (+)';

    nok is-point-in-polygon([1.5, -0.8], @nc),
                'lower half of non-convex polygon (-)';
    nok is-point-in-polygon([1.5, 0.8], @nc),
                'lower half of non-convex polygon (+)';

    ok  is-point-in-polygon([1.5, -1.3], @nc),
                'lower half of non-convex polygon (-)';

    #     (0, 1) +
    #           / \
    #          /   \
    # (-1, 0) +     + (1, 0)
    #          \   /
    #           \ /
    #     (0, -1) +

    my @diamond = parse-line('-1,0 0,1 1,0 0,-1');
    ok  is-point-in-polygon([0, 0], @diamond),
            'diamond: test point above a polygon node';
    nok is-point-in-polygon([1, 1], @diamond),
            'diamond: upper right';
    nok  is-point-in-polygon([0, 2], @diamond),
            'diamond: above two polygon nodes';

    done_testing;
}

Readability

Very much so.

Consistency

The sub name vertical-intersection should probably have been pluralized, since what it returns is a number, not a boolean. Very minor nit.

Clarity of intent

The action at the heat of the battle is very carefully explained.

Look at those comments with ASCII graphs in the tests! That's love, man.

Algorithmic efficiency

Not really a concern in this task. The time complexity is linear on the number of points.

Idiomatic use of Perl 6

.split(/\s+/) on line 4 is better spelled .words.

The @poly Z @poly.rotate on line 34 does more neatly and with less fuss what other solutions spend much more on. No sliding window utility functions required.

Sub in a sub. Neat.

Brevity

The algorithmic code ends on line 48. The remaining 65% are spent on test code. When non-brevity is of that nature, who's to complain?