http://qs1969.pair.com?node_id=109325

mitd has asked for the wisdom of the Perl Monks concerning the following question:

Recently vroom dropped into CB looking for a some code that would answer the question that given a polygon and a point does point live inside the polygon. I am sure Tim has found or built his solution by now but it got to thinking since I was in a an ojective kind of mood I might take a crack for my own amusement.

First I dug up an algorithm1 and came up with some classes.

Point
X
Y
Line
Point1
Point2
Polygon
SortedPoints[1..n]

Next we need, as per algorithm three methods/functions:

Now where to stick methods?? Well inside could certainly live inside Polygon but both same_line and intersect deal with Lines(plural). So create a Lines class ?? Maybe just christian them all Helpers and stick 'em in a GeometryHelper class.

I have a sneaking suspicion there is a twisted Perly path to this design and that is why I am seeking a sober second opinion from the Monk collective.

Note

  1. This is not a solicitation for code.
  2. If you suspect this is homework you are correct. In my spare time (thats the time I have after; 'tending to the needs of my wife and 7 kids, sheperding a small pod of programmers and trying to keep my customers happy) I am doing a double PHD in Philosphy (Thesis: What is the Point) and Physics (Thesis: Where is the Point)

1 ... given a polygon represented as an array of points and another point, determine whether the point is inside or outside. Draw a line segment form the point long enough thats its endpoint is guaranteed to be outside the polygon and count the number of lines from the polygon it crosses. If LX mod 2 != 0 then point is inside polygon.

pp 312-317
Algorithms, Sedgewick, Addison-Wesley, 1983

mitd-Made in the Dark
'My favourite colour appears to be grey.'

Replies are listed 'Best First'.
Re: Points, Lines. Polygons OO my
by mirod (Canon) on Aug 31, 2001 at 13:50 UTC

    I remember that problem from school, a long time ago, and you have to be careful with a naive implementation of the algorithm. Angle points should _sometimes_ count as 2 points.

    Just to clarify, here is the problem with angles and edges:

    Warning: crappy ASCII art follows.

              _     ___
             | \   /   |
             |  \ /    |
     (1)_ _ _|_ _v_ _ _|_ _  3 intersections
             |         |
              \        |
     (2)_ _ _ _\_ _ _ _|_ _  2 intersections
               /       |
              /        |
     (3)_ _ _|_ _ _ _ _|_ _  3 intersections
             |    /\   |
             |   /  \  |
     (4)_ _ _|__/_ _ \_|_ _  ? intersections
    

    The solution for angle points is to count them in only if the line they belong to goes down (or up, it doesn't matter, just choose one direction), thus (1) would have 2 intersections (the angle does not count) and (3) would have 4 (the angle counts twice, once for each line).

    The solution for an edge is to count it as 2 intersections, one for each end, thus (4) would have 4 intersections.

Re: Points, Lines. Polygons OO my
by Zaxo (Archbishop) on Aug 31, 2001 at 13:08 UTC

    The Wolf Book, pp441-445 has an implementation which is C-like and unreliable for corner cases. The algorithm is the same one you cite: does a ray from the test point cross edges an even or odd number of times? If odd, it's an interior point.

    My take on the OO issues you raise derives from the hierarchy of 0- to 1- to 2-dimensional geometry. Interior and exterior are properties of of each particular polygon, so I suppose that $poly->is_interior($point) is natural. A Line has-a pair of Points to define it, so Point methods are available to it. A Polygon has-a list of Points as vertices, or equivalently a list of Lines with common endpoints. Point and Line methods are available to Polygon.

    After Compline,
    Zaxo

Re: Points, Lines. Polygons OO my
by blakem (Monsignor) on Aug 31, 2001 at 12:53 UTC
    I don't quite get it.. If this isn't a code solicitation, are you looking for a discussion of how the objects might behave, or at clever ways of attacking the problem...

    My first thought would be to:

    Given Point A(x,y) and Polygon P with vertices V1..Vn
    1.) Create Point B(x,y) such that Bx is greater than all x values of the vertices, and By is greater than all y values of the vertices
    2.) Check each edge of P (including endpoints, but excluding those with both endpoints on AB) to see if it intersects segment AB, if so $count++. (fairly trivial, left to excercise for the reader.)
    3.) for (V1..Vn) {$count-- if V is on AB} as they were double counted in step 2
    4.) $inside = $count%2;

    I think I could probably golf that in 150 chars or less... ;-)

    Or, maybe you were looking for a discussion on your objects...

    -Blake

Re: Points, Lines. Polygons OO my
by jbert (Priest) on Aug 31, 2001 at 16:41 UTC

    IMHASO, (...And Sober...)

    I wouldn't get worried about the fact that intersect operates on more than one Line. So does 'equals' - you just take another member of the class as an arg and its all quite natural.

    As I suspect you think too, the Helpers idea is barbaric. Why use objects at all in that case?

    So one OO way to do it (in pseudo-code definitions) would be:

    Polygon: ->new( Point p1, Point p2, ... ); ->has_inside( Point p ); # return true/false ->get_outside_point(); # return Point outside the polygon ->first_line(); # return 'line 1' - reset counter ->next_line(); # return next_line, incr counter # undef if no more Line: ->new( Point x, Point y ); ->intersects( Line l ); # return true/false # Is this what you mean by 'same_line'? ->equals( Line l ); # return true/false

    Lastly, I like to name 'private' methods with a leading underscore. So if ->same_line or ->equals is really only needed by ->intersects you might want to rename it to ->_equals.

    (This is just documentation obviously. Anyone with the MilliClue (or KiloClue) who wishes to violate the published API is free to. This is perl, after all.)

    However, in this particular case it seems like a sensible function to have as part of the object's "published" API and so I probably wouldn't do it.

What fun...
by Rhose (Priest) on Aug 31, 2001 at 22:19 UTC
    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
Re: Points, Lines. Polygons OO my
by kapper (Chaplain) on Aug 31, 2001 at 20:30 UTC

    Its not just for fun that most game programmers work strictly in triangles.. problems such as the one you mentioning becomes so much faster to calculate...

    Simple solution: Make sure you are only dealing with triangles.. create a static point for each triangle, which you know is within it.. now make a line from that point to your point, check if it intersects with any of the lines in your triangle... if true, its outside, false, inside.

    Most general solution: I believe this was allready mentioned, but create a line between your point and any point which you know is outside of the polygon.. now count the number of intersections between this line, and edges in your polygon.. if its odd, your point is inside, otherwise outside.. (note: do not count intersections with edges, just ignore them... and this solution does not only work with triangles, but any polygon)

    Alternative solution: This one will also only work with triangles.. project your point onto two of the edges in the polygon. Yous should now have two fractions t1 and t2 telling you where your point projected onto the two edges.. if both t1 and t2 are between 0 and 1, and t1+t2<1 then your point lies within..

    Anyways, have fun... if you need more solutions, search for pages about the nonzero winding number rule... I'm too tired to explain it now, but it should be easy to find a good page on it... (Note: this method will also work well with polygons that intersect with temselves to generate hollow areas within.. )

Re: Points, Lines. Polygons OO my
by SilverB1rd (Scribe) on Aug 31, 2001 at 19:00 UTC
    Based on my game programing experience (not alot) with collision detection one of the best ways to test for intersection is to brake the polygon into triangles and then test each to see if the point is inside it.

    ------
    PT - Perl Tanks %100 Perl programming game
    The Price of Freedom is Eternal Vigilance

Re: Points, Lines. Polygons OO my
by MZSanford (Curate) on Sep 07, 2001 at 13:11 UTC
    I was working on a GD based module, when i came up with a functional fix (so, it's not pretty, but mostly just to prove it works).
    #!/usr/bin/perl use GD; my $image = new GD::Image(110,110); my $red = $image->colorAllocate(255,0,0); my $blue = $image->colorAllocate(0,0,255); my $white = $image->colorAllocate(255,255,255); $image->fill(0,0,$white); my $poly = new GD::Polygon; $poly->addPt(50,0); ### add your points $poly->addPt(99,99); $poly->addPt(0,99); $image->polygon($poly); ### do the work my $base_point = [109,109]; # known outside my $test_point = [50,50]; # unknown $image->fill($test_point->[0],$test_point->[1],$red); my $clrindex = $image->getPixel($base_point->[0],$base_point->[1]); if ($clrindex == $red) { warn "Point is outside of polygon."; exit 0; } else { warn "Point is inside of polygon."; exit 1; }
    so, if it is the answer you seek, i like this way ... if it is the mathmatics of it (which it probably is), this is not use.
    can't sleep clowns will eat me
    -- MZSanford