Re: [Algorithms] Point inside polygon

[Kevin L. <lac...@in...>]

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
>