ward@eplrx7.uucp (Rick Ward) (12/06/89)
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.
For those who are wondering, a convex hull is a surface which covers a
set of points without any concave patches(i.e. it only connects the
outermost points).
Thanks in advance.
Rick
--
Rick Ward | E.I. Dupont Co.
uunet!eplrx7!ward | Engineering Physics Lab
(302) 695-7395 | Wilmington, Delaware 19898
Just Say When. | Mail Stop: E357-302
--
The UUCP Maileremcalc@sugar.hackercorp.com (William M. Schmidt) (12/06/89)
The Jarvis march method in 2-d can be generalized to 3-d. It's called "gift wrapping" because that's what it resembles. A good reference for these sort of geometrical problems is "Computational Geometry - An Introduction" by Preparata and Shamos, 1985, Springer-Verlag. I believe that this is an O(N^2) algorithm in 3-d. -- Bill Schmidt | Texas Accelerator Center | "Eagles may soar, but a worm never emcalc@sugar.hackercorp.com | gets sucked into a jet engine"
glenn@eos.UUCP (Glenn Meyer) (12/07/89)
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