Hi all, I'm considering representing some areas of a 2d game-map with complex polygons made up of line segments (since the borders for each map-space are geopolitical in nature and are thus very irregularly-shaped). However, these polygons are then likely to be concave. I would like to be able to calculate whether a given XY coordinate lies WITHIN or OUTSIDE OF each polygon. Any tips or ideas on how best to code this sort of algorithm up? Thanks! Take care, --HB Edited by - HBringer on April 1, 2002 8:04:06 AM

I remember seeing a few fast algorithms to solve this problem in Computer Graphics: Principles and Practice, but I don''t have it handy. I think one of the fastest point-in-polygon test was to shoot a ray from infinity to your point, and count the number of times it hits an edge before reaching the point. If this number is even, then the point is outside, but if it''s odd, then the point is inside. Of course, the speed of this algorithm depends largely on how fast you can intersect polygon edges with a ray, but it has the advantage of working with both convex and concave polygons.

Cédric

i can help you. i once was looking for a solution too. now i''m glad i can pass it on. it might not be that easy, but if u''re good enough, u''ll get it. this app uses a very nice line intersection algo, if u can find it and implement it in ur app, my congrats. (i handled it, so it''s not that hard)

ftp://ftp.gdmag.com/pub/src/jan99.zip

good luck, and have fun!

p.s. it''s in lander.zip file.

Another standard reply:

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.