From: Kevin Lackey <lackkevi@in...>  20031230 22:22:38

Forgot to add this is an O(n) solution as you have to check for an intersection for every ray with the edge..... I don't know of a faster less intensive solution . Kevin Uma Cabaca, Um Arame, Um Pedaco de Pau. On Tue, 30 Dec 2003, Kevin Lackey wrote: > If the polygon is on the same plane just cast a ray in any direction from > the point and count the number of collisions with the edges of the > polygon. Odd the point is inside, even the point is outside. > > Kevin > > Uma Cabaca, Um Arame, Um Pedaco de Pau. > > On Tue, 30 Dec 2003, Tyler Ohlsen wrote: > > > 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 > > > > >  > 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 > 