Ray-casting algorithm

constant ε = 0.0001;
 
sub ray-hits-seg([\Px,\Py], [[\Ax,\Ay], [\Bx,\By]] --> Bool) {
    Py += ε if Py == Ay | By;
 
    if Py < Ay or Py > By or Px > (Ax max Bx) {
	False;
    }
    elsif Px < (Ax min Bx) {
	True;
    }
    else {
	my \red  = Ax == Bx ?? Inf !! (By - Ay) / (Bx - Ax);
	my \blue = Ax == Px ?? Inf !! (Py - Ay) / (Px - Ax);
	blue >= red;
    }
}

sub point-in-poly(@point, @polygon --> Bool) {
    so 2 R% [+] gather for @polygon -> @side {
	take ray-hits-seg @point, @side.sort(*.[1]);
    }
}
 
my %poly =
    squared => 
	 [[[ 0.0,  0.0], [10.0,  0.0]],
	  [[10.0,  0.0], [10.0, 10.0]],
	  [[10.0, 10.0], [ 0.0, 10.0]],
	  [[ 0.0, 10.0], [ 0.0,  0.0]]],
    squaredhole =>
	 [[[ 0.0,  0.0], [10.0,  0.0]],
	  [[10.0,  0.0], [10.0, 10.0]],
	  [[10.0, 10.0], [ 0.0, 10.0]],
	  [[ 0.0, 10.0], [ 0.0,  0.0]],
	  [[ 2.5,  2.5], [ 7.5,  2.5]],
	  [[ 7.5,  2.5], [ 7.5,  7.5]],
	  [[ 7.5,  7.5], [ 2.5,  7.5]],
	  [[ 2.5,  7.5], [ 2.5,  2.5]]],
    strange =>
	 [[[ 0.0,  0.0], [ 2.5,  2.5]],
	  [[ 2.5,  2.5], [ 0.0, 10.0]],
	  [[ 0.0, 10.0], [ 2.5,  7.5]],
	  [[ 2.5,  7.5], [ 7.5,  7.5]],
	  [[ 7.5,  7.5], [10.0, 10.0]],
	  [[10.0, 10.0], [10.0,  0.0]],
	  [[10.0,  0.0], [ 2.5,  2.5]],
	  [[ 2.5,  2.5], [ 0.0,  0.0]]],  # conjecturally close polygon
    exagon =>
	 [[[ 3.0,  0.0], [ 7.0,  0.0]],
	  [[ 7.0,  0.0], [10.0,  5.0]],
	  [[10.0,  5.0], [ 7.0, 10.0]],
	  [[ 7.0, 10.0], [ 3.0, 10.0]],
	  [[ 3.0, 10.0], [ 0.0,  5.0]],
	  [[ 0.0,  5.0], [ 3.0,  0.0]]];
 
my @test-points =
	  [  5.0,  5.0],
	  [  5.0,  8.0],
	  [-10.0,  5.0],
	  [  0.0,  5.0],
	  [ 10.0,  5.0],
	  [  8.0,  5.0],
	  [ 10.0, 10.0];
 
for <squared squaredhole strange exagon> -> $polywanna {
    say "$polywanna";
    my @poly = %poly{$polywanna}[];
    for @test-points -> @point {
	say "\t(@point.fmt('%.1f',','))\t{ point-in-poly(@point, @poly) ?? 'IN' !! 'OUT' }";
    }
}

Output:

squared
        (5.0,5.0)       IN
        (5.0,8.0)       IN
        (-10.0,5.0)     OUT
        (0.0,5.0)       OUT
        (10.0,5.0)      IN
        (8.0,5.0)       IN
        (10.0,10.0)     OUT
squaredhole
        (5.0,5.0)       OUT
        (5.0,8.0)       IN
        (-10.0,5.0)     OUT
        (0.0,5.0)       OUT
        (10.0,5.0)      IN
        (8.0,5.0)       IN
        (10.0,10.0)     OUT
strange
        (5.0,5.0)       IN
        (5.0,8.0)       OUT
        (-10.0,5.0)     OUT
        (0.0,5.0)       OUT
        (10.0,5.0)      IN
        (8.0,5.0)       IN
        (10.0,10.0)     OUT
exagon
        (5.0,5.0)       IN
        (5.0,8.0)       IN
        (-10.0,5.0)     OUT
        (0.0,5.0)       OUT
        (10.0,5.0)      IN
        (8.0,5.0)       IN
        (10.0,10.0)     OUT

Last updated