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

[perlcapt]

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
# [e-mail]
#
# 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;
}