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:  a "plumbline" algorithm
Picture
The problem of point location is to find in which polygon a reference point lies.  A typical application of this problem is an interactive map:  if I click on the map, how can the software tell me if I clicked in Pennsylvania or Ohio?

The plumbline algorithm is based on a very simple idea.  From the reference point (for example, where I click on the map), drop a vertical line.  This is called a plumbline, since vertical lines in the construction industry were once made by attaching a heavy lead weight, called a plumb or plumb-bob, to a string.  The weight pulled the string to a vertical alignment, and the carpenter could then mark the vertical line.  In the plumbline algorithm, we count the number of times the plumbline intersects sides of a polygon.  Obviously, if the plumbline does not intersect any sides of the polygon, the reference point is not in the polygon.  Equally obvious:  if the plumbline intersects just one side of the polygon, then the reference point is inside the polygon.  Generally:  if the plumbline intersects an odd number of sides of the polygon, then the reference point is inside the polygon.

The efficiency algorithm depends on the number of sides of all polygons which could contain the reference point.  

In some cases, one can quickly decide if the polygon intersects a side or not:  if both ends of the side lie to the left or right of the plumbline, then there can be no intersections.

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