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 in Three Dimensions:  an Incremental algorithm
Picture
This incremental algorithm begins with the convex hull of four nonplanar points:  a tetrahedron.  Each successive point is tested to see if the new point lies within the previous hull.  If it does, nothing more need be done.  If it does not, then the new point must become a vertex of the new hull.  From the point of view of the new point, determine which facets of the old hull are visible.  The edges of visible facets shared by an invisible facet comprise the "horizon" as seen from the new point.  The visible facets must be removed, and new facets constructed.  The new facets include an edge of the horizon and the new point.

Click the Download button at the right to download all movies described on this page, not including the virtual reality movies.

Virtual Reality Movies

To improve understanding of algorithms in three-dimensional computational geometry, virtual reality (VR) "object movies" of some scenes within the algorithm have been constructed.  The user may manipulate these VR movies as if he were handling a real object and turning it in his hands.  After the viewer has "handled" the scene, he may continue to play the time-line movie to complete the algorithm.

Movies which include both timeline and VR portions cannot be viewed easily with the usual QuickTime player. A unique player is constructed which allows the user to move from timeline to VR seamlessly.  This idea is presented here as an experiment. The VR movies are not included in the download. Please write for further information.



download
Proudly powered by Weebly