Point-in-Polygon: the Winding Number
|
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. There is one movie available, based on a map of Worcester County, Maryland, USA. Click on the Download button at the right to obtain both versions of this movie in a zipped file. |