 The stupid question is the question not asked PerlMonks

### What fun...

by Rhose (Priest)
 on Aug 31, 2001 at 22:19 UTC ( #109470=note: print w/replies, xml ) Need Help??

in reply to Points, Lines. Polygons OO my

First off, this simple question ruined my day -- how am I supposed to think out work-related 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 != @mPolygon[-2] ||
+@mPolygon != @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 != \$pPoint[Y1]);

#-- Add the X intersect for the line
if (\${\$mLine{\$_}}[Y1] == \${\$mLine{\$_}}[Y2])
{
@mSortX = sort \$pPoint[X1],\${\$mLine{\$_}}[X1],\${\$mLine{\$_}}[X2];
if (\$mSortX == \$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
[download]```

Log In?
 Username: Password:

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

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (5)
As of 2019-08-19 20:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
If you were the first to set foot on the Moon, what would be your epigram?

Results (141 votes). Check out past polls.

Notices?