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] - \$pPoint[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