Anonymous user
Ray-casting algorithm: Difference between revisions
perl
(→{{header|Python}}: scroll regions to reduce length) |
(perl) |
||
Line 364:
end program Pointpoly</lang>
=={{header|Perl}}==
<lang perl>use strict;
use List::Util qw(max min);
sub point_in_polygon
{
my ( $point, $polygon ) = @_;
my $count = 0;
foreach my $side ( @$polygon ) {
$count++ if ray_intersect_segment($point, $side);
}
return ($count % 2 == 0) ? 0 : 1;
}
my $eps = 0.0001;
my $inf = 1e600;
sub ray_intersect_segment
{
my ($point, $segment) = @_;
my $A = $segment->[0];
my $B = $segment->[1];
my @P = @$point; # copy it
($A, $B) = ($B, $A) if ( $A->[1] > $B->[1] );
$P[1] += $eps if ( ($P[1] == $A->[1]) || ($P[1] == $B->[1]) );
return 0 if ( ($P[1] < $A->[1]) || ( $P[1] > $B->[1]) || ($P[0] > max($A->[0],$B->[1]) ) );
return 1 if ( $P[0] < min($A->[0], $B->[0]) );
my $m_red = ($A->[0] != $B->[0]) ? ( $B->[1] - $A->[1] )/($B->[0] - $A->[0]) : $inf;
my $m_blue = ($A->[0] != $P[0]) ? ( $P[1] - $A->[1] )/($P[0] - $A->[0]) : $inf;
return ($m_blue >= $m_red) ? 1 : 0;
}</lang>
Testing:
<lang perl># the following are utilities to use the same Fortran data...
sub point
{
return [shift, shift];
}
sub create_polygon
{
my ($pts, $sides) = @_;
my @poly = ();
for(my $i = 0; $i < (scalar(@$sides)-1); $i += 2) {
push @poly, [ $pts->[$sides->[$i]-1], $pts->[$sides->[$i+1]-1] ];
}
return @poly;
}
my @pts = ( point(0,0), point(10,0), point(10,10), point(0,10),
point(2.5,2.5), point(7.5,2.5), point(7.5,7.5), point(2.5,7.5),
point(0,5), point(10,5),
point(3,0), point(7,0), point(7,10), point(3,10) );
my @squared = create_polygon(\@pts, [ 1,2, 2,3, 3,4, 4,1 ] );
my @squaredhole = create_polygon(\@pts, [ 1,2, 2,3, 3,4, 4,1, 5,6, 6,7, 7,8, 8,5 ] );
my @strange = create_polygon(\@pts, [ 1,5, 5,4, 4,8, 8,7, 7,3, 3,2, 2,5 ] );
my @exagon = create_polygon(\@pts, [ 11,12, 12,10, 10,13, 13,14, 14,9, 9,11 ]) ;
my @p = ( point(5,5), point(5, 8), point(-10, 5), point(0,5), point(10,5), &
point(8,5), point(10,10) );
foreach my $pol ( "squared", "squaredhole", "strange", "exagon" ) {
print "$pol\n";
my @rp = eval('@' . $pol);
foreach my $tp ( @p ) {
print "\t($tp->[0],$tp->[1]) " .
( point_in_polygon($tp, \@rp) ? "INSIDE" : "OUTSIDE" ) . "\n";
}
}</lang>
=={{header|Python}}==
| |||