dean@CIS.OHIO-STATE.EDU (Andrew Dean) (11/17/89)
Hi. Does anybody have C source for a program to compute the CONVEX HULL of a set of points in 3D? INPUT : a set of points (Xi,Yi,Zi). OUTPUT: the polygons forming the convex hull surface OR the half-spaces defined by the facets of the hull. A fast algorithm would be nice, but brute force would be OK since the point sets will not be very large. Thanks for any help. andy dean dean@cis.ohio-state.edu
glenn@eos.UUCP (Glenn Meyer) (11/17/89)
dean@CIS.OHIO-STATE.EDU (Andrew Dean) writes: >Hi. >Does anybody have C source for a program to compute the >CONVEX HULL of a set of points in 3D? >INPUT : a set of points (Xi,Yi,Zi). >OUTPUT: the polygons forming the convex hull surface OR > the half-spaces defined by the facets of the hull. >A fast algorithm would be nice, but brute force would >be OK since the point sets will not be very large. >Thanks for any help. >andy dean dean@cis.ohio-state.edu I don't have the source code, but there's a thorough description of the convex hull algorithm in "Computational Geometry: An Introduction," by Franco P. Preparata and Michael Ian Shamos (New York: Springer-Verlag, 1985), pp. 131-148. The fastest algorithm you can hope to achieve in the general case has a complexity of order NlogN, where N is the number of points. ------------- Glenn Meyer glenn%{eos,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