Convex Hull in Three Dimensions: an Incremental algorithm
|
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. |