# RE: Point in Polygon Routine

From: Bill Odom <wno...@intrasection.com>
Tue, 27 Jun 2000 13:44:40 -0500
```Jack asked:
> Does anyone know of a module which will tell me if an x,y value lies
within
> a polygon (i.e. @xyarray)?

>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__

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

```