Point in Polygon: Winding Number
how many times around did you wind? one and you're in; zero, you're not
The winding number is the number of complete turns an observer makes while traversing a polygon. If the observer is outside the polygon, positive and negative angles will cancel, and the observer will make no turns; if the observer is inside the polygon, she will make one complete turn. The number of turns will be different for compound polygons (such as a polygon with a hole), or in other topologies; but for planar simple polygons, the winding number will be either zero or one.
The winding number requires the computation of an inverse trigonometric function, and it requires examining every pair of adjacent vertices. Consequently, it is no better than the plumbline algorithm in complexity (that is, O(N), and may, in fact, be slower because the computation at each vertex is more difficult.
Four movies are available; the map shows Worcester County, Maryland (less resolution than other examples). One of the movies is a version with pauses for questions. Remember the guidelines for use of these movies.
|
|
|
|
|
|
