| Store | Cart

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)?

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

Recent Messages in this Thread
Dunnigan,Jack [Edm] Jun 27, 2000 12:04 am
Joseph P. Discenza Jun 27, 2000 05:41 pm
Bill Odom Jun 27, 2000 06:44 pm
Messages in this thread