Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

Re: Determing whether point falls inside or outside a complex polygon

by Stevie-O (Friar)
on Nov 09, 2004 at 22:08 UTC ( #406536=note: print w/replies, xml ) Need Help??

in reply to Determing whether point falls inside or outside a complex polygon

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.

$"=$,,$_=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
  • Comment on Re: Determing whether point falls inside or outside a complex polygon
  • Download Code

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://406536]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (4)
As of 2018-03-24 20:05 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (299 votes). Check out past polls.