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 "QuickHull" algorithm
Picture
The "QuickHull" algorithm is so named because of its similarity to the QuickSort algorithm.  The algorithm is recursive, and, at each step of the algorithm, points are identified which are internal, and therefore never again are needed for the vertices of the convex hull.

This work was done, wholly or in part, by Kevin R. Camasi, F&M'01, and Anne Fairchild Peacock, F&M '02.

The algorithm is order O(n log n).  It proceeds by finding the bottommost, topmost, leftmost and rightmost points in the set.  These must lie on the convex hull.  A quadrilateral is drawn with these four points as its vertices.  Then, each edge is examined to see if point like outside the edge.  The point which lies furthest outside the edge must like on the convex hull; therefore the original edge is removed, and new edges to the new exterior point are added.  This process is repeated recursively for each of the four edges of the original quadrilateral.

This work was done, wholly or in part, by Anne Fairchild Peacock, F&M '02, and Kevin R. Camasi, F&M '01.

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