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