Prof. Dr. Jay Martin Anderson
Professor Emeritus of Computer Science, Franklin & Marshall College
  • home
  • Development
    • Gallery
    • Stop and Pray
    • Stations at St. Thomas
    • PricePer
    • What's It Cost?
    • my own
    • at F&M
    • for clients
  • Small Gallery
  • LVC
  • Visualization
    • Algorithm Visualization >
      • Binary Space Partition
      • Convex Hull >
        • Extreme Point algorithm
        • Extreme Edge algorithm
        • "Gift Wrap" algorithm
        • Incremental algorithm
        • Incremental algorithm in three dimensions
        • "QuickHull" algorithm
      • Delaunay triangulation >
        • Incremental algorithm
        • from the Voronoi diagram
      • Line intersection >
        • a "brute force" algorithm
        • Sweepline algorithm
      • Motion planning
      • Point-in-Polygon >
        • Plumbline algorithm
        • Trapezoidal Map
        • Winding Number
      • Polygon triangulation >
        • "Art Gallery" Problem
        • Recursive algorithm
        • Make Monotone Polygons
        • Triangulate a Monotone Polygon
      • Voronoi diagram >
        • Fortune's algorithm
        • Intersection of Half-Planes
        • Quadtree algorithm
    • Data Visualization
  • OpenGL
    • OpenGL for Apple Software Developers
  • iBooks
  • about me
    • contact
Point-in-Polygon:  the Winding Number
Picture
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.

download
Proudly powered by Weebly