Keep It Simple, Stupid 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??

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

Create A New User
Node Status?
node history
Node Type: note [id://406184]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (5)
As of 2018-03-21 03:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (263 votes). Check out past polls.

Notices?