Thread: [Algorithms] Point inside polygon
Brought to you by:
vexxed72
From: Tyler O. <Xa...@ho...> - 2003-12-30 21:19:07
|
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 |
From: Matt P. <mat...@ph...> - 2003-12-30 21:42:11
|
"Tyler Ohlsen" <Xa...@ho...> writes: > 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. Eric Haines has a nice article on this topic in Graphics Gems IV: "Point in Polygon Strategies", page 25. He covers a fair amount of history, discusses various approaches, and compares the performance of his implementations of a number of them. To make a long story short, the best approach for the situation you describe (not necessarily convex, ~10,000 vertices), is probably to superimpose a 2D grid over the polygon's bounding box, and for each cell in the grid, determine whether the cell is inside the polygon, outside, or if one or more edges passes through it. Then, many of your lookups should be constant-time (for all points inside cells that are completely inside and outside), and you only need to do real work for the remaining ones. An implementation of this as well as the other methods described in his article are available here: http://www1.acm.org/pubs/tog/GraphicsGems/gemsiv/ptpoly_haines/ Another good reference on this topic is Schneider and Eberly's "Geometric Tools for Computer Graphics", section 13.3. In particular, they have a good discussion of how to handle some of the tricky corner cases that come up with this issue. -matt -- Matt Pharr ma...@ph... <URL:http://graphics.stanford.edu/~mmp> ======================================================================= In a cruel and evil world, being cynical can allow you to get some entertainment out of it. --Daniel Waters |
From: Kevin L. <lac...@in...> - 2003-12-30 22:11:21
|
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 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
From: Kevin L. <lac...@in...> - 2003-12-30 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 > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > 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 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
From: Alex M. <am...@cs...> - 2003-12-31 11:10:28
|
Even with this solution, it's not necessarily true that you require O(n) time. You'll end up building acceleration structures that allow you to do the ray cast in (something like) log(n) time. Just look at standard raytracing acceleration structures. (Regular grid, quad/octtree, etc). It's essentially going have the same properties as the other presented acceleration structures. Of course with any of this stuff comes the burden of knowing what kind of polygons you're dealing with. If you have "nasty" polygons much of the time, it can still be really hard. That is, for some acceleration structure, it's usually easy to construct an input that foils it. Alex >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. |
From: Charles B. <cb...@cb...> - 2003-12-30 23:08:20
|
There are about a million ways to do this. Most involve some sort of tree. Galaxy3 has an integer convex hull tree that would be fun, and is O(logN) but certainly not the fastest way. A BSP would be good. Probably best is just a sorted list of spans in one of the dimensions which you can then binary search to find all the segments in that coordinate span on that dimensions, and then do the simple 2d-side test on all those segments. This is O(N) in pathological cases, but you can fix that. -------------------------------------------------------------------------------------------- Charles Bloom email "cb" http://www.cbloom.com |
From: Alen L. <ale...@cr...> - 2003-12-31 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" <Xa...@ho...> To: "Game Dev Algorithms List" <gda...@li...> 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 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
From: Tom P. <ga...@fa...> - 2003-12-31 17:27:45
|
Alen Ladavac wrote: > 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). You could build the BSP with concave polys, too, just realizing that some polygons may straddle a partition. It doesn't much matter though, because at the leaf node you're either in or out. -tom! |
From: Alen L. <ale...@cr...> - 2004-01-03 08:57:05
|
Heh - that's what I said: "not convex"=="concave". :) If the polygon is convex, then BSP is much less useful. ----- Original Message ----- From: "Tom Plunket" <ga...@fa...> To: <gda...@li...> Sent: Wednesday, December 31, 2003 6:27 PM Subject: Re: [Algorithms] Point inside polygon > Alen Ladavac wrote: > > > 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). > > You could build the BSP with concave polys, too, just realizing > that some polygons may straddle a partition. It doesn't much > matter though, because at the leaf node you're either in or out. > > -tom! > > > ------------------------------------------------------- > 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 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
From: Denis S. <su...@at...> - 2004-01-03 11:41:22
|
Hello Tyler, Wednesday, December 31, 2003, 12:19:04 AM, you wrote: TO> I'm looking for a fast algorithm to determine if a 2D point is inside a TO> polygon. The polygons I am using are not necessarily convex and they TO> are made up of any number of points (up to 10000 points in some cases). TO> The main concern of this algorithm is performance. Because of the high TO> number of points per polygon and the high number of polygons this TO> program needs to check in a limited amount of time, I am looking for an TO> algorithm that does not need to check every line segment of the polygon TO> in question. TO> I understand that you can throw out some polygons by quickly checking to TO> see if the point is outside the bounding box of the polygon. Basically, TO> I understand that there are techniques that would allow you to TO> significantly speed up the algorithm that checks every line segment, but TO> that is not what I am looking for. TO> Would anyone know of an algorithm that will return true only if the TO> given point is within the given polygon without having to look through TO> every line segment of the polygon? TO> Thanks, TO> Tyler There is relatively simple algo known as "method of stripes". It's not specially for polygons, but for any planar linear graph (edges are line segments, edge intersections only in verts) method: sort verts by y-coord. Draw the imaginary horizontal line through each vertex. This gives N+1 horizontal stripes. Now, for any point P you can find the stripe in O(logN) by P.y. And there is no verts in any of the stripes: only edges, without intersections (even number of edges (M), odd number of trapezoids (M+1) ). Then for each stripe, sort the edges in left-to-right order. So you can binary search the trapezoid by P.x: if trapezoid index is odd, then point is inside poly. This gives you O(logN) request time, but with O(N^2 * logN) pre-process time and O(N^2) memory cost. -- Best regards, Denis |