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 "trapezoidal map" 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 trapezoidal map algorithm makes use of the binary search algorithm, the fastest way to search for something in a sorted collection.  The map is divided into trapezoids by drawing a vertical line through every vertex of every polygon in the map.  The very thin slivers are sorted by their horizontal coordinate, and so it is fast to find in which sliver the reference point lies.  But, each sliver is composed of a number of trapezoids, and so it is then possible to find in which trapezoid the reference point lies.  If we are careful to remember to which polygon a trapezoid belongs, we will quickly discover in which polygon the reference point lies.

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

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