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
Polygon Triangulation:  Make Monotone Polygons
Picture
In addition to the recursive algorithm, we can also triangulate a polygon in a two-step algorithm:  first, decompose the polygon into monotone  polygons; then triangulate the monotone polygons.  A polygon is monotone if, when traversing from the uppermost vertex to the lowermost vertex along either the left or right side, one never moves up; that is, while going down, one goes consistently down or level.

The algorithm begins by characterizing the vertices as stop, start, split, merge, or regular vertices.  Split (or merge) vertices lie above (or below) their neighbors, and are therefore vertices which make the polygon not monotone.  The algorithm proceeds to connect split and merge vertices, thereby making monotone polygons.

Click on the Download button at the right to download a zipped file of all movies described on this page.

download
Proudly powered by Weebly