Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

comment on

( #3333=superdoc: print w/replies, xml ) 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: #-- 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

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 How to display code and escape characters are good places to start.
Log In?

What's my password?
Create A New User
Domain Nodelet?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (5)
As of 2023-02-05 10:44 GMT
Find Nodes?
    Voting Booth?
    I prefer not to run the latest version of Perl because:

    Results (31 votes). Check out past polls.