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;
}
Very much so.
The sub name vertical-intersection
should probably have been pluralized,
since what it returns is a number, not a boolean. Very minor nit.
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.
Not really a concern in this task. The time complexity is linear on the number of points.
.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.
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?