Anonymous Monk has asked for the
wisdom of the Perl Monks concerning the following question:
Fellows Monks!
I am banging my head as to where to get started with this one. (this is not homework). I need your help/insight.
I have a field of data points that fall inside and outside a complex polygon. The goal is to determine which points reside inside, which outside and perform a different operation on either respective type.
Obviously I want to do this using perl; my generalized thoughts on the matter for how to do it are:
the plan
 first: define an equation for the complex polygon?
 second: determine points inside, do something to them
 third: determine points outside, do different something to them
Essentially, I have the outline as to what I want to do, but no real clue as to where to begin.
Is there a module(s) out there that will do this sort of thing?
Any help that you can provide in this matter will be greatly appreciated!!!!
Thanks in advance.
Re: Determing whether point falls inside or outside a complex polygon by bgreenlee (Friar) on Nov 08, 2004 at 16:59 UTC 
 [reply] 

That depends on how you define the interior of a polygon which intersects itself. If you want to account for the possibility that your point is "inside twice", the most general solution is to compute the winding number.
 [reply] 
Re: Determing whether point falls inside or outside a complex polygon by fglock (Vicar) on Nov 08, 2004 at 17:06 UTC 
 [reply] [d/l] 

#
# 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[$i1][1] <= $point[1]) { # start y <= P.y
if ($points[$i][1] > $point[1]) { # // an upward crossing
if (CrossProduct([$points[$i1],$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[$i1],$points[$i],$pointref]) < 0) {
# point right of edge
$wn; # have a valid down intersect
}
}
}
}
return $wn;
}
 [reply] [d/l] 
Re: Determing whether point falls inside or outside a complex polygon by pg (Canon) on Nov 08, 2004 at 17:12 UTC 
Find any point that is beyond the right most point of the polygon. That's easy, just find a x that is greater than the greatest x of the polygon, with any reasonable y. Call this point ForSureOutside.
Then draw a line between the point under investigation and ForSureOutside. (Not physically draw, but find the equation of the line with those two points)
If this line intersects with any line SEGMENT that form the polygon, then the point under investigation is inside the polygon.
 [reply] 

Not quite. If the line intersects with an *odd* number of polygon segments, then the point is inside the polygon (see the drawings on that link I posted above).
 [reply] 

 [reply] 

X
A
B Y fso
C
Z
Ascii graphic above includes polygon XYZ, fso is the point "for sure outside" as described above and points A and C for which there is no interesection between FSOA or FSOC and any line in the polygon.
However, for point B there is an intersection, very close to the vertex at Y (ie, it may be on XY or on YZ) and another on XZ.  [reply] 
Re: Determing whether point falls inside or outside a complex polygon by itub (Priest) on Nov 08, 2004 at 17:39 UTC 
You can also take a look at the book Mastering Algorithms with Perl. The chapter about geometric algorithms is available on the web for free at http://www.oreilly.com/catalog/maperl/. The code from the examples in the book is also available.  [reply] 
Re: Determing whether point falls inside or outside a complex polygon by bobf (Monsignor) on Nov 08, 2004 at 20:55 UTC 
 [reply] 
Re: Determing whether point falls inside or outside a complex polygon by punch_card_don (Curate) on Nov 09, 2004 at 21:59 UTC 
I was going to say that the missing piece of information to be able to give you a relevant reply is: how is your polygon defined? There are lots of possibilities in many coordinate systems, but I bet you just have the xy coordinates of the corners in the same coordinate system as your data points.
On that assumption, the very first post provides a very elegant method.
Here's how you might code it in Perl, in very basic style for clarity.
A further assumption is that you have already been told how to build the polygon from the corner coordinates  you know which dots are connected to which so you don't have to try every polygon possible for a given set of corner points.
#assume we start with the corner points ordered in order of drawing th
+e polygon
@x = (x1, x2, x3, ....);
@y = (y1, y2, y3, ....);
# determine the equations of each side
for $i (0 .. $#@x1) {
$m[$i] = ($y[$i+1]  $y[$i])/($x[$i+1]  $x[$i]);
$b[$i] = $y[$i]  $m[$i]*$x[$i];
}
#test each point
@data_x= (dx1, dx2, dx3, ...);
@data_y= (dy1, dy2, dy3, ...);
for $i (0 .. $#data_y) {
#find intersection of the line y = $data_y[$i] with each polygon
+side
for $j (0 .. $#x1) {
if ($m[$j] != 0) {
$x_intsxn = ($data_y[$i]  $b[$j])/$m[$j];
#does that intersection occur within the side's le
+ngth?
if (($x_intsxn > $x[$j] && $x_intsxn < $x[$j+1]) 
+ ($x_intsxn > $x[$j] && $x_intsxn < $x[$j+1])) {
#is this intersection to the right or left of
+ the point?
if ($x_intsxn > $data_x[$i]) {$right++;}
else {$left++;}
}
}
}
#test odd/even interesections
if ($left % 2 && $right % 2) {odd number means point inside polyg
+on, do 'insidepoint' stuff or flag point as inside}
else {flag point as outside}
}
 [reply] [d/l] 
Re: Determing whether point falls inside or outside a complex polygon by StevieO (Friar) on Nov 09, 2004 at 22:08 UTC 
Amazingly enough: I had to do this once.
Background for those who don't care:
I once wrote a program that converted .WAD (game level) files from Doom format to versions playable in Hexen (whose engine is based on Doom's, but has certain significant changes).
Most things weren't a problem  even the increased player height (56 units in Doom, 64 in Hexen  so low ceilings needed to be raised, and proper textures added if necessary).
However, in Doom, a teleporter can only specify the "sector" (think of a sector as a room  the walls and floor and ceiling) you teleported to, and a special object called a 'teleport destination' was placed inside that sector. (This was due to a limitation in how line specials were processed).
In Hexen's advanced engine, the teleporter directly specified the ID of the teleport destination object.
Thus, I had a problem: How could I find the teleport destination object that was inside the sector?
Topology tells us an easy way to tell if a point is "inside" or "outside" a 2D object: draw a line from that point, to outside the object. If the line crosses an odd number of border lines, it is inside the object. If it crosses an even number, it is outside the object.
My solution was simple: Find any point that's *outside* the object. (This is easily accomplished by finding the maximum X coordinate of all the vertices, then finding the maximum Y coordinate of all the vertices, then choosing the point (X+1, Y+1).)
Imagine a hypothetical line (A,B)(X+1,Y+1) with (A,B) being the point to be tested.
Now count the number of line segments in your polygon that *intersect* the line (A,B)(X+1,Y+1).
If the count is odd: (A,B) is inside the polygon.
If the count is even, then it is outside.
StevieO
$"=$,,$_=q>\p4<6 8p<M/_<('=>
.q>.<4KI<l2$<6%s!<qn#F<>;$,
.=pack'N*',"@{[unpack'C*',$_]
}"for split/</;$_=$,,y[AZ az]
{}cd;print lc
 [reply] [d/l] 

