Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re^2: Determing whether point falls inside or outside a complex polygon

by perlcapt (Pilgrim)
on Nov 08, 2004 at 19:28 UTC ( #406184=note: print w/ replies, xml ) Need Help??


in reply to Re: Determing whether point falls inside or outside a complex polygon
in thread Determing whether point falls inside or outside a complex polygon

Here is the code from the Math::Geometry::Planar for discussion. Notice that Msr. Van de Pol uses the winding number method.

# # Copyright (c) 2002 Danny Van de Pol - Alcatel Telecom Belgium # danny.vandepol@alcatel.be # # Free usage under the same Perl Licence condition. # # OTHER METHODS DELETED ###################################################################### +########## # # The winding number method has been cused here. Seems to # be the most accurate one and, if well written, it matches # the performance of the crossing number method. # The winding number method counts the number of times a polygon # winds around the point. If the result is 0, the points is outside # the polygon. # # args: reference to polygon object # reference to a point # sub IsInsidePolygon { my ($pointsref,$pointref) = @_; my @points = @$pointsref; if (@points < 3) { # polygon should at least have 3 points ... carp("Can't run inpolygon: polygon should have at least 3 points") +; return; } if (! $pointref) { carp("Can't run inpolygon: no point entered"); return; } my @point = @$pointref; my $wn; # thw winding number counter for (my $i = 0 ; $i < @points ; $i++) { if ($points[$i-1][1] <= $point[1]) { # start y <= P.y if ($points[$i][1] > $point[1]) { # // an upward crossing if (CrossProduct([$points[$i-1],$points[$i],$pointref]) > 0) { # point left of edge $wn++; # have a valid up intersect } } } else { # start y > P.y (no test need +ed) if ($points[$i][1] <= $point[1]) { # a downward crossing if (CrossProduct([$points[$i-1],$points[$i],$pointref]) < 0) { # point right of edge $wn--; # have a valid down intersect } } } } return $wn; }
perlcapt
-ben


Comment on Re^2: Determing whether point falls inside or outside a complex polygon
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://406184]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2014-10-24 21:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (137 votes), past polls