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
[download]