Re: Point Inside Polygon - Ray Method
- From: James Waldby <j-waldby@xxxxxxxx>
- Date: Thu, 20 Apr 2006 14:59:25 -0600
Larry Hammick wrote:
....
Keith A. Lewis wrote:
There is an alternative method called "winding". It counts the number of
times the polygon goes around the point.
If the final winding count is 0, the point is outside. If it's 1, the
polygon went counterclockwise around the point.
Note, winding numbers may exceed 1 if the polygon isn't simple.
Three rays are enough; any three distinct ones will do.
Related, but fancier, is this suped-up version of Sperner's lemma:
http://planetmath.org/encyclopedia/SpernersLemma.html
Perhaps strict convexity would be a sufficient condition for three
rays to be enough; it seems to me it ought to be, but the link below
says point inclusion can be tested in O(log n) time for convex polygons.
http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
compares crossing-number and winding-number point-is-in-polygon
algorithms, and says that at the moment winding number calculations
can be done slightly faster (although of same asymptotic efficiency).
-jiw
.
- Follow-Ups:
- Re: Point Inside Polygon - Ray Method
- From: Virgil
- Re: Point Inside Polygon - Ray Method
- References:
- Point Inside Polygon - Ray Method
- From: Narek Saribekyan
- Re: Point Inside Polygon - Ray Method
- From: Keith A. Lewis
- Re: Point Inside Polygon - Ray Method
- From: Larry Hammick
- Point Inside Polygon - Ray Method
- Prev by Date: Re: Proclus Quotation
- Next by Date: Re: Help! I think this is a simple math problem.
- Previous by thread: Re: Point Inside Polygon - Ray Method
- Next by thread: Re: Point Inside Polygon - Ray Method
- Index(es):
Relevant Pages
|
