Just another Perl shrine PerlMonks

### comment on

 Need Help??
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[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

In reply to What fun... by Rhose
in thread Points, Lines. Polygons OO my by mitd

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or or How to display code and escape characters are good places to start.

Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (1)
As of 2022-01-28 06:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2022, my preferred method to securely store passwords is:

Results (73 votes). Check out past polls.

Notices?