Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!agate!eos!glenn
From: glenn@eos.UUCP (Glenn Meyer)
Newsgroups: comp.graphics
Subject: Re: Convex hulls
Keywords: How do you calculate the convex hull in 3d?
Message-ID: <5782@eos.UUCP>
Date: 7 Dec 89 03:33:27 GMT
References: <1989Dec5.220421.10486@eplrx7.uucp>
Organization: NASA Ames Research Center, California
Lines: 25

ward@eplrx7.uucp (Rick Ward) writes:


>Does anyone have any references or, even better, source code on how to
>calculate the convex hull of a set of points in three dimensions?  I 
>have seen the paper by DCS Allison and MT Noga on how to calculate the
>convex hull in two dimensions, but a three dimensional solution doesn't
>come readily to mind.  

"Computational Geometry: An Introduction," by Franco P. Preparata and 
Michael Ian Shamos (New York: Springer-Verlag, 1985) devotes about 
90 pages to the solution and applications of convex hull algortihms. 
The book discusses an order NlogN algorithm, where N is the number 
of points in 3D space, and also describes an algorithm that approximates 
the convex hull.

Glenn Meyer
glenn@eos.arc.nasa.gov
glenn%carma@ames.arc.nasa.gov

-- 
Glenn Meyer (glenn%carma@{io,aurora,eos,pioneer}.arc.nasa.gov)
CARMA/Sterling Software 
NASA-Ames, M.S. 233-14, Moffett Field, Ca.  94035
Office telephone # 415-694-4804