Beefy Boxes and Bandwidth Generously Provided by pair Networks
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[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

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?