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
Convex Hull:  the "Gift Wrap" algorithm
Picture
The "gift wrap algorithm" has an acceptable efficiency, quadratic order, or O(N2).  This means that the algorithm will run 100 times longer (in time) for ten times as many points.

Example: for the point set, find the lowest vertex (or, you could find the highest, rightmost, or leftmost).  This vertex must be on the convex hull.  Then, find the point which makes the smallest angle to the horizontal drawn through the lowest point, in a counterclockwise direction.  This point must also be on the convex hull.  Then, continue to find the point which makes the smallest angle with the preceding edge.  Continue until you return to the lowest point.  These edges constitute the convex hull.

The algorithm is called the "gift wrap" algorithm because it resembles wrapping paper around an arbitrary collection of points, as if they were a strange-shaped package.

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

DOWNLOAD
Proudly powered by Weebly