Path: utzoo!news-server.csri.toronto.edu!rutgers!dimacs.rutgers.edu!mips!spool.mu.edu!snorkelwacker.mit.edu!stanford.edu!leland.Stanford.EDU!elaine4.Stanford.EDU!artkuo
From: artkuo@elaine4.Stanford.EDU (arthur kuo)
Newsgroups: comp.graphics
Subject: Re: Convex hull of a set of 3D vertices
Message-ID: <1991Mar14.065930.9512@leland.Stanford.EDU>
Date: 14 Mar 91 06:59:30 GMT
References: <1991Mar4.200121.2762@leland.Stanford.EDU>
Sender: news@leland.Stanford.EDU (Mr News)
Organization: Stanford University - AIR
Lines: 25

In article <1991Mar4.200121.2762@leland.Stanford.EDU> artkuo@elaine4.stanford.edu (arthur kuo) writes:

>I have a set of points in 3D space, and I want the convex hull of this set.
>Also, I want to find the polygons that define the convex hull, not just the
>vertices that are in the hull.  Thanks.

Enough people have asked me to forward this information that I have decided
to post it to the net.

Chuck Kirschman, Brian Guenter, and Larry Baer were kind enough to point me
to the following reference:

   A. M. Day. "Implementation of an algorithm to find the convex hull
   of a set of 3-d points." ACM Transactions on Graphics, v. 9 #1.
   Jan 1990.  pp. 105-132.

The article includes a listing of the Pascal implementation of the algorithm.
I hope to get the C code from someone (name withheld to protect privacy).
One drawback to the algorithm is that it does not handle coplanar points,
but the author claims that he is working on it.

Art Kuo 

--
Neuromuscular Systems Laboratory, Stanford University