From: Alen Ladavac <alenlml@cr...>  20031231 11:16:06

If the polygons are not convex, and you can afford some preprocessing time to prepare polygons in advance, you can do it in O(log N) using a BSP. For best runtime performance, try to nudge the BSP building heuristic towards balanced tree (same number of edges on both sides of a split). Alen  Original Message  From: "Tyler Ohlsen" <Xalviz@...> To: "Game Dev Algorithms List" <gdalgorithmslist@...> Sent: Tuesday, December 30, 2003 21:19 Subject: [Algorithms] Point inside polygon > I'm looking for a fast algorithm to determine if a 2D point is inside a > polygon. The polygons I am using are not necessarily convex and they > are made up of any number of points (up to 10000 points in some cases). > > > The main concern of this algorithm is performance. Because of the high > number of points per polygon and the high number of polygons this > program needs to check in a limited amount of time, I am looking for an > algorithm that does not need to check every line segment of the polygon > in question. > > I understand that you can throw out some polygons by quickly checking to > see if the point is outside the bounding box of the polygon. Basically, > I understand that there are techniques that would allow you to > significantly speed up the algorithm that checks every line segment, but > that is not what I am looking for. > > Would anyone know of an algorithm that will return true only if the > given point is within the given polygon without having to look through > every line segment of the polygon? > > Thanks, > Tyler > > >  > This SF.net email is sponsored by: IBM Linux Tutorials. > Become an expert in LINUX or just sharpen your skills. Sign up for IBM's > Free Linux Tutorials. Learn everything from the bash shell to sys admin. > Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 