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