mitd has asked for the wisdom of the Perl Monks concerning the following question:
Recently vroom dropped into CB looking for a some code that would
answer the question that given a polygon and a point does point live
inside the polygon. I am sure Tim has found or built his
solution by now but it got to thinking since I was in a an ojective
kind of mood I might take a crack for my own amusement.
First I dug up an algorithm^{1} and came up with some classes.


Polygon

SortedPoints[1..n]


Next we need, as per algorithm three methods/functions:
 inside
 intersect  used by inside
 same_line  used by intersect
Now where to stick methods?? Well inside could certainly live inside
Polygon but both same_line and intersect deal with
Lines(plural). So create a Lines class ?? Maybe just christian
them all Helpers and stick 'em in a GeometryHelper class.
I have a sneaking suspicion there is a twisted Perly path to this
design and that is why I am seeking a sober second opinion from the
Monk collective.
Note
 This is not a solicitation for code.
 If you suspect this is homework you are correct. In my spare time
(thats the time I have after; 'tending to the needs of my wife and 7
kids, sheperding a small pod of programmers and trying to keep my
customers happy) I am doing a double PHD in Philosphy (Thesis: What is
the Point) and Physics (Thesis: Where is the Point)
^{1} ... given a polygon represented as an array of points and
another point, determine whether the point is inside or outside. Draw
a line segment form the point long enough thats its endpoint is
guaranteed to be outside the polygon and count the number of lines
from the polygon it crosses. If LX mod 2 != 0 then point is inside
polygon.
pp 312317
Algorithms, Sedgewick, AddisonWesley, 1983
mitdMade in the Dark
'My favourite colour appears to be grey.'
Re: Points, Lines. Polygons OO my
by mirod (Canon) on Aug 31, 2001 at 13:50 UTC

I remember that problem from school, a long time ago, and you have to be careful with a naive implementation of the algorithm. Angle points should _sometimes_ count as 2 points.
Just to clarify, here is the problem with angles and edges:
Warning: crappy ASCII art follows.
_ ___
 \ / 
 \ / 
(1)_ _ __ _v_ _ __ _ 3 intersections
 
\ 
(2)_ _ _ _\_ _ _ __ _ 2 intersections
/ 
/ 
(3)_ _ __ _ _ _ __ _ 3 intersections
 /\ 
 / \ 
(4)_ _ ___/_ _ \__ _ ? intersections
The solution for angle points is to count them in only if the line they belong to goes down (or up, it doesn't matter, just choose one direction), thus (1) would have 2 intersections (the angle does not count) and (3) would have 4 (the angle counts twice, once for each line).
The solution for an edge is to count it as 2 intersections, one for each end, thus (4) would have 4 intersections.
 [reply] 
Re: Points, Lines. Polygons OO my
by Zaxo (Archbishop) on Aug 31, 2001 at 13:08 UTC

The Wolf Book, pp441445 has an implementation which is Clike and unreliable for corner cases. The algorithm is the same one you cite: does a ray from the test point cross edges an even or odd number of times? If odd, it's an interior point.
My take on the OO issues you raise derives from the hierarchy of 0 to 1 to 2dimensional geometry. Interior and exterior are properties of of each particular polygon, so I suppose that $poly>is_interior($point) is natural. A Line hasa pair of Points to define it, so Point methods are available to it. A Polygon hasa list of Points as vertices, or equivalently a list of Lines with common endpoints. Point and Line methods are available to Polygon.
After Compline, Zaxo
 [reply] 
Re: Points, Lines. Polygons OO my
by blakem (Monsignor) on Aug 31, 2001 at 12:53 UTC

I don't quite get it.. If this isn't a code solicitation, are you looking for a discussion of how the objects might
behave, or at clever ways of attacking the problem...
My first thought would be to:
Given Point A(x,y) and Polygon P with vertices V1..Vn
1.) Create Point B(x,y) such that Bx is greater than all x values of the vertices, and By is greater than all y values of the vertices
2.) Check each edge of P (including endpoints, but excluding those with both endpoints on AB) to see if it intersects segment AB, if so $count++. (fairly trivial, left to excercise for the reader.)
3.) for (V1..Vn) {$count if V is on AB} as they were double counted in step 2
4.) $inside = $count%2;
I think I could probably golf that in 150 chars or less... ;)
Or, maybe you were looking for a discussion on your objects...
Blake
 [reply] 
Re: Points, Lines. Polygons OO my
by jbert (Priest) on Aug 31, 2001 at 16:41 UTC

IMHASO, (...And Sober...)
I wouldn't get worried about the fact that intersect operates on more than one Line. So does 'equals'  you just take another member of the class as an arg and its all quite natural.
As I suspect you think too, the Helpers idea is barbaric. Why use objects at all in that case?
So one OO way to do it (in pseudocode definitions) would be:
Polygon:
>new( Point p1, Point p2, ... );
>has_inside( Point p ); # return true/false
>get_outside_point(); # return Point outside the polygon
>first_line(); # return 'line 1'  reset counter
>next_line(); # return next_line, incr counter
# undef if no more
Line:
>new( Point x, Point y );
>intersects( Line l ); # return true/false
# Is this what you mean by 'same_line'?
>equals( Line l ); # return true/false
Lastly, I like to name 'private' methods with a leading underscore. So if >same_line or >equals is really only needed by >intersects you might want to rename it to >_equals.
(This is just documentation obviously. Anyone with the MilliClue (or KiloClue) who wishes to violate the published API is free to. This is perl, after all.)
However, in this particular case it seems like a sensible function to have as part of the object's "published" API and so I probably wouldn't do it.
 [reply] [d/l] 
What fun...
by Rhose (Priest) on Aug 31, 2001 at 22:19 UTC

First off, this simple question ruined my day  how am I supposed to think out workrelated tasks when something this important is waiting? *Grins*
While you did not ask for any code, I found the problem interesting, so threw together a quick "solution".
Please note: instead of drawing a line to a point I knew to be outside the polygon, I took a horizontal line (Y = point{y}) and examined all the X coordinates where this line intersected the polygon. By ordering these X coordinates you end up with an outside/inside/outside/inside pattern. The only "sticky" spots I found were vertices which lie on the horizontal line, and points which lie on one of the polygon's horizontal lines.
Anyway, here is the code. (If anyone has suggestion on better coding practices, I am always up for that as well! *Smiles*)
use strict;
#
# Script: within.pl
# Purpose: Check if a point lies within a polygon
#
# Author: Rhose
# Date: August 31, 2001
#
# Define variables
my @mPolygon;
# Define subroutines
sub CheckPoint
{
# Get parameters
my @pPoint = @_;
# Define constants
use constant TRUE => 1;
use constant FALSE => 0;
use constant LOCATION => {
0 => 'Outside',
1 => 'Inside',
2 => 'On'
};
use constant X1 => 0;
use constant Y1 => 1;
use constant X2 => 2;
use constant Y2 => 3;
# Define local variables
my $mLoc; # Location of the point (outside, inside, or on)
my $mOnHoriz; # Points on a horizontal line cause problems; this
+ catches them
my $mPtr; # A pointer used when processing arrays
my $mSlope; # The slop of an individual line
my @mSortY; # Temporary array to see if a line intersects the
+Y = $pPoint[Y1] line
my @mSortX; # Temporary array to see if the point is on a line
my @mX; # Array of all X coords where the Y = $pPoint[Y1]
+line intersects the polygon
my %mLine; # Array of lines which compose the polygon
# Make sure the last point is the same as the first (complete the
+polygon)
push @mPolygon, @mPolygon[0,1] if (@mPolygon[0] != @mPolygon[2] 
+@mPolygon[1] != @mPolygon[1]);
# Build the lines array
for ($mPtr = 0; $mPtr <= $#mPolygon  3; $mPtr+=2)
{
push @{$mLine{'L'.($mPtr/2)}}, @mPolygon[$mPtr..$mPtr+3];
}
# Check for lines which intersect the Y = $pPoint[Y1] line
$mOnHoriz = FALSE;
foreach (keys %mLine)
{
# Skip lines where the point's Y is not within the line's Ys
@mSortY = sort $pPoint[Y1],${$mLine{$_}}[Y1],${$mLine{$_}}[Y2];
next if ($mSortY[1] != $pPoint[Y1]);
# Add the X intersect for the line
if (${$mLine{$_}}[Y1] == ${$mLine{$_}}[Y2])
{
@mSortX = sort $pPoint[X1],${$mLine{$_}}[X1],${$mLine{$_}}[X2];
if ($mSortX[1] == $pPoint[X1])
{
$mOnHoriz = TRUE;
last;
}
}
else
{
$mSlope = (${$mLine{$_}}[X2]  ${$mLine{$_}}[X1])/(${$mLine{$_}}
+[Y2]  ${$mLine{$_}}[Y1]);
push @mX, ${$mLine{$_}}[X2]  ($mSlope * (${$mLine{$_}}[Y2]  $p
+Point[Y1]));
}
}
# Sort the X coordinates
@mX = sort @mX;
# Find out where the point is
if ($mOnHoriz)
{
$mLoc = 2;
}
else
{
$mLoc = 0;
for ($mPtr = 0; $mPtr <= $#mX; $mPtr++)
{
# Check for on the line
$mLoc = 2 if ($mX[$mPtr] == $pPoint[X1]);
# Skip vertices
next if ($mX[$mPtr] == $mX[$mPtr+1]);
# Stop if past the point
last if ($mX[$mPtr] >= $pPoint[X1]);
# Toggle the outside/inside location flag
$mLoc = 1  $mLoc;
}
}
# Display the results
print 'Point (',$pPoint[X1],',',$pPoint[Y1],') is ',LOCATION>{$mLoc
+}," the polygon.\n";
}
# Check some points
print "mirod's shape:\n";
@mPolygon = (1,0,1,1,2,2,1,3,1,5,2,5,4,4,5,5,6,5,6,0,5,0,4,1,3,0);
CheckPoint(0.5,4);
CheckPoint(1.5,1.5);
CheckPoint(1.5,2);
CheckPoint(2,4);
CheckPoint(3.5,3);
CheckPoint(4,1);
CheckPoint(4,4);
CheckPoint(4,5);
CheckPoint(5,5);
CheckPoint(5.5,5);
CheckPoint(6,2);
CheckPoint(6,6);
CheckPoint(7,3);
print "\n\n";
print "Triangle:\n";
@mPolygon = (1,0,3,0,3,3);
CheckPoint(1,0);
CheckPoint(3,0);
CheckPoint(3,3);
CheckPoint(2,1.5);
CheckPoint(3,1);
CheckPoint(2,0);
CheckPoint(2.5,1);
CheckPoint(0,2);
CheckPoint(4,2);
CheckPoint(2,1);
# Exit
exit(0);
# End of script
 [reply] [d/l] 
Re: Points, Lines. Polygons OO my
by kapper (Chaplain) on Aug 31, 2001 at 20:30 UTC

Its not just for fun that most game programmers work strictly in triangles.. problems such as the one you mentioning becomes so much faster to calculate...
Simple solution: Make sure you are only dealing with triangles.. create a static point for each triangle, which you know is within it.. now make a line from that point to your point, check if it intersects with any of the lines in your triangle... if true, its outside, false, inside.
Most general solution: I believe this was allready mentioned, but create a line between your point and any point which you know is outside of the polygon.. now count the number of intersections between this line, and edges in your polygon.. if its odd, your point is inside, otherwise outside.. (note: do not count intersections with edges, just ignore them... and this solution does not only work with triangles, but any polygon)
Alternative solution: This one will also only work with triangles.. project your point onto two of the edges in the polygon. Yous should now have two fractions t1 and t2 telling you where your point projected onto the two edges.. if both t1 and t2 are between 0 and 1, and t1+t2<1 then your point lies within..
Anyways, have fun... if you need more solutions, search for pages about the nonzero winding number rule... I'm too tired to explain it now, but it should be easy to find a good page on it... (Note: this method will also work well with polygons that intersect with temselves to generate hollow areas within.. )
 [reply] 
Re: Points, Lines. Polygons OO my
by SilverB1rd (Scribe) on Aug 31, 2001 at 19:00 UTC

 [reply] 
Re: Points, Lines. Polygons OO my
by MZSanford (Curate) on Sep 07, 2001 at 13:11 UTC

I was working on a GD based module, when i came up with a functional fix (so, it's not pretty, but mostly just to prove it works).
#!/usr/bin/perl
use GD;
my $image = new GD::Image(110,110);
my $red = $image>colorAllocate(255,0,0);
my $blue = $image>colorAllocate(0,0,255);
my $white = $image>colorAllocate(255,255,255);
$image>fill(0,0,$white);
my $poly = new GD::Polygon;
$poly>addPt(50,0); ### add your points
$poly>addPt(99,99);
$poly>addPt(0,99);
$image>polygon($poly);
### do the work
my $base_point = [109,109]; # known outside
my $test_point = [50,50]; # unknown
$image>fill($test_point>[0],$test_point>[1],$red);
my $clrindex = $image>getPixel($base_point>[0],$base_point>[1]);
if ($clrindex == $red) {
warn "Point is outside of polygon.";
exit 0;
} else {
warn "Point is inside of polygon.";
exit 1;
}
so, if it is the answer you seek, i like this way ... if it is the mathmatics of it (which it probably is), this is not use.
_{can't sleep clowns will eat me}
 MZSanford
 [reply] [d/l] 

