Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Determing whether point falls inside or outside a complex polygon

by Anonymous Monk
on Nov 08, 2004 at 16:54 UTC ( #406116=perlquestion: print w/ replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Fellows Monks!
I am banging my head as to where to get started with this one. (this is not homework). I need your help/insight.
I have a field of data points that fall inside and outside a complex polygon. The goal is to determine which points reside inside, which outside and perform a different operation on either respective type.
Obviously I want to do this using perl; my generalized thoughts on the matter for how to do it are:
    the plan---
  • first: define an equation for the complex polygon?
  • second: determine points inside, do something to them
  • third: determine points outside, do different something to them
Essentially, I have the outline as to what I want to do, but no real clue as to where to begin.
Is there a module(s) out there that will do this sort of thing?
Any help that you can provide in this matter will be greatly appreciated!!!!
Thanks in advance.

Comment on Determing whether point falls inside or outside a complex polygon
Re: Determing whether point falls inside or outside a complex polygon
by bgreenlee (Friar) on Nov 08, 2004 at 16:59 UTC
      That depends on how you define the interior of a polygon which intersects itself. If you want to account for the possibility that your point is "inside twice", the most general solution is to compute the winding number.
Re: Determing whether point falls inside or outside a complex polygon
by fglock (Vicar) on Nov 08, 2004 at 17:06 UTC
      Here is the code from the Math::Geometry::Planar for discussion. Notice that Msr. Van de Pol uses the winding number method.
      # # Copyright (c) 2002 Danny Van de Pol - Alcatel Telecom Belgium # danny.vandepol@alcatel.be # # Free usage under the same Perl Licence condition. # # OTHER METHODS DELETED ###################################################################### +########## # # The winding number method has been cused here. Seems to # be the most accurate one and, if well written, it matches # the performance of the crossing number method. # The winding number method counts the number of times a polygon # winds around the point. If the result is 0, the points is outside # the polygon. # # args: reference to polygon object # reference to a point # sub IsInsidePolygon { my ($pointsref,$pointref) = @_; my @points = @$pointsref; if (@points < 3) { # polygon should at least have 3 points ... carp("Can't run inpolygon: polygon should have at least 3 points") +; return; } if (! $pointref) { carp("Can't run inpolygon: no point entered"); return; } my @point = @$pointref; my $wn; # thw winding number counter for (my $i = 0 ; $i < @points ; $i++) { if ($points[$i-1][1] <= $point[1]) { # start y <= P.y if ($points[$i][1] > $point[1]) { # // an upward crossing if (CrossProduct([$points[$i-1],$points[$i],$pointref]) > 0) { # point left of edge $wn++; # have a valid up intersect } } } else { # start y > P.y (no test need +ed) if ($points[$i][1] <= $point[1]) { # a downward crossing if (CrossProduct([$points[$i-1],$points[$i],$pointref]) < 0) { # point right of edge $wn--; # have a valid down intersect } } } } return $wn; }
      perlcapt
      -ben
Re: Determing whether point falls inside or outside a complex polygon
by pg (Canon) on Nov 08, 2004 at 17:12 UTC

    Find any point that is beyond the right most point of the polygon. That's easy, just find a x that is greater than the greatest x of the polygon, with any reasonable y. Call this point ForSureOutside.

    Then draw a line between the point under investigation and ForSureOutside. (Not physically draw, but find the equation of the line with those two points)

    If this line intersects with any line SEGMENT that form the polygon, then the point under investigation is inside the polygon.

      Not quite. If the line intersects with an *odd* number of polygon segments, then the point is inside the polygon (see the drawings on that link I posted above).

      -b

        You are right ;-) However with one addition, if the point of insect is also the intersect of two line segments of the polygon, you have to be careful.

      Don't think so.
      
      
                     X                   
                                           A
            B                       Y fso
      
                                 C
               Z
      

      Ascii graphic above includes polygon XYZ, fso is the point "for sure outside" as described above and points A and C for which there is no interesection between FSO-A or FSO-C and any line in the polygon.

      However, for point B there is an intersection, very close to the vertex at Y (ie, it may be on XY or on YZ) and another on XZ.

Re: Determing whether point falls inside or outside a complex polygon
by itub (Priest) on Nov 08, 2004 at 17:39 UTC
    You can also take a look at the book Mastering Algorithms with Perl. The chapter about geometric algorithms is available on the web for free at http://www.oreilly.com/catalog/maperl/. The code from the examples in the book is also available.
Re: Determing whether point falls inside or outside a complex polygon
by bobf (Monsignor) on Nov 08, 2004 at 20:55 UTC
Re: Determing whether point falls inside or outside a complex polygon
by punch_card_don (Curate) on Nov 09, 2004 at 21:59 UTC
    I was going to say that the missing piece of information to be able to give you a relevant reply is: how is your polygon defined? There are lots of possibilities in many coordinate systems, but I bet you just have the x-y coordinates of the corners in the same coordinate system as your data points.

    On that assumption, the very first post provides a very elegant method.

    Here's how you might code it in Perl, in very basic style for clarity.

    A further assumption is that you have already been told how to build the polygon from the corner coordinates - you know which dots are connected to which so you don't have to try every polygon possible for a given set of corner points.

    #assume we start with the corner points ordered in order of drawing th +e polygon @x = (x1, x2, x3, ....); @y = (y1, y2, y3, ....); # determine the equations of each side for $i (0 .. $#@x-1) { $m[$i] = ($y[$i+1] - $y[$i])/($x[$i+1] - $x[$i]); $b[$i] = $y[$i] - $m[$i]*$x[$i]; } #test each point @data_x= (dx1, dx2, dx3, ...); @data_y= (dy1, dy2, dy3, ...); for $i (0 .. $#data_y) { #find intersection of the line y = $data_y[$i] with each polygon +side for $j (0 .. $#x-1) { if ($m[$j] != 0) { $x_intsxn = ($data_y[$i] - $b[$j])/$m[$j]; #does that intersection occur within the side's le +ngth? if (($x_intsxn > $x[$j] && $x_intsxn < $x[$j+1]) | +| ($x_intsxn > $x[$j] && $x_intsxn < $x[$j+1])) { #is this intersection to the right or left of + the point? if ($x_intsxn > $data_x[$i]) {$right++;} else {$left++;} } } } #test odd/even interesections if ($left % 2 && $right % 2) {odd number means point inside polyg +on, do 'insidepoint' stuff or flag point as inside} else {flag point as outside} }
Re: Determing whether point falls inside or outside a complex polygon
by Stevie-O (Friar) on Nov 09, 2004 at 22:08 UTC
    Amazingly enough: I had to do this once.

    Background for those who don't care:

    I once wrote a program that converted .WAD (game level) files from Doom format to versions playable in Hexen (whose engine is based on Doom's, but has certain significant changes).

    Most things weren't a problem -- even the increased player height (56 units in Doom, 64 in Hexen -- so low ceilings needed to be raised, and proper textures added if necessary).

    However, in Doom, a teleporter can only specify the "sector" (think of a sector as a room -- the walls and floor and ceiling) you teleported to, and a special object called a 'teleport destination' was placed inside that sector. (This was due to a limitation in how line specials were processed).

    In Hexen's advanced engine, the teleporter directly specified the ID of the teleport destination object. Thus, I had a problem: How could I find the teleport destination object that was inside the sector?


    Topology tells us an easy way to tell if a point is "inside" or "outside" a 2-D object: draw a line from that point, to outside the object. If the line crosses an odd number of border lines, it is inside the object. If it crosses an even number, it is outside the object.

    My solution was simple: Find any point that's *outside* the object. (This is easily accomplished by finding the maximum X coordinate of all the vertices, then finding the maximum Y coordinate of all the vertices, then choosing the point (X+1, Y+1).)

    Imagine a hypothetical line (A,B)-(X+1,Y+1) with (A,B) being the point to be tested.

    Now count the number of line segments in your polygon that *intersect* the line (A,B)-(X+1,Y+1).

    If the count is odd: (A,B) is inside the polygon. If the count is even, then it is outside.

    --Stevie-O
    $"=$,,$_=q>|\p4<6 8p<M/_|<('=> .q>.<4-KI<l|2$<6%s!<qn#F<>;$, .=pack'N*',"@{[unpack'C*',$_] }"for split/</;$_=$,,y[A-Z a-z] {}cd;print lc

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://406116]
Approved by muntfish
Front-paged by Old_Gray_Bear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (9)
As of 2014-08-20 12:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (113 votes), past polls