Jack asked:
> Does anyone know of a module which will tell me if an x,y value lies
within
> a polygon (i.e. @xyarray)?
How about a subroutine?
>From _Mastering Algorithms with Perl_ (an excellent book that
everyone should immediately run right out and buy), p.443-444:
#!/usr/bin/perl
# point_in_polygon ( $x, $y, @xy )
#
# Point ($x,$y), polygon ($x0, $y0, $x1, $y1, ...) in @xy.
# Returns 1 for strictly interior points, 0 for strictly exterior
# points. For the boundary points the situation is more complex and
# beyond the scope of this book. The boundary points are
# exact, however: if a plane is divided into several polygons, any
# given point belongs to exactly one polygon.
#
# Derived from the comp.graphics.algorithms FAQ,
# courtesy of Wm. Randolph Franklin.
#
sub point_in_polygon {
my ( $x, $y, @xy ) = @_;
my $n = @xy / 2; # Number of points in polygon.
my @i = map { 2 * $_ } 0 .. (@xy/2); # The even indices of @xy.
my @x = map { $xy[ $_ ] } @i; # Even indices: x-coordinates.
my @y = map { $xy[ $_ + 1 ] } @i; # Odd indices: y-coordinates.
my ( $i, $j ); # Indices.
my $side = 0; # 0 = outside, 1 = inside.
for ( $i = 0, $j = $n - 1 ; $i < $n; $j = $i++ ) {
if (
(
# If the y is between the (y-) borders ...
( ( $y[ $i ] <= $y ) && ( $y < $y[ $j ] ) ) ||
( ( $y[ $j ] <= $y ) && ( $y < $y[ $i ] ) )
)
and
# ...the (x,y) to infinity line crosses the edge
# from the ith point to the jth point...
($x
<
( $x[ $j ] - $x[ $i ] ) *
( $y - $y[ $i ] ) / ( $y[ $j ] - $y[ $i ] ) + $x[ $i ] )) {
$side = not $side; # Jump the fence.
}
}
return $side ? 1 : 0;
}
@polygon = ( 1, 1, 3, 5, 6, 2, 9, 6, 10, 0, 4,2, 5, -2);
print "( 3, 4): ", point_in_polygon( 3, 4, @polygon ), "\n";
print "( 3, 1): ", point_in_polygon( 3, 1, @polygon ), "\n";
print "( 3,-2): ", point_in_polygon( 3,-2, @polygon ), "\n";
print "( 5, 4): ", point_in_polygon( 5, 4, @polygon ), "\n";
print "( 5, 1): ", point_in_polygon( 5, 1, @polygon ), "\n";
print "( 5,-2): ", point_in_polygon( 5,-2, @polygon ), "\n";
print "( 7, 4): ", point_in_polygon( 7, 4, @polygon ), "\n";
print "( 7, 1): ", point_in_polygon( 7, 1, @polygon ), "\n";
print "( 7,-2): ", point_in_polygon( 7,-2, @polygon ), "\n";
__END__
This and other samples from the book can be downloaded from
ftp.oreilly.com/pub/examples/perl/algorithms/examples.zip
--Bill Odom
-----Original Message-----
From: perl...@listserv.ActiveState.com
[mailto:perl...@listserv.ActiveState.com]On Behalf Of
Dunnigan,Jack [Edm]
Sent: Monday, June 26, 2000 7:04 PM
To: 'Perl-list-win32'
Subject: Point in Polygon Routine
Does anyone know of a module which will tell me if an x,y value lies within
a polygon (i.e. @xyarray)?
Jack
_______________________________________________
Perl-Win32-Users mailing list
Perl...@listserv.ActiveState.com
http://listserv.ActiveState.com/mailman/listinfo/perl-win32-users