## 3D convex hull algorithms

### 3D convex hull algorithms

I'm looking for references/implementations
of 3D convex hull algorithms.  I'm familiar
with 2D algorithms, but not 3D.  I'll
appreciate any pointers.

Larry Bergman

### 3D convex hull algorithms

There is a whole chapter on CH algorithms in

Herbert Edelsbrunner
Algorithms in Combinatorial Geometry
(EATC monographs on theoretical computer science; v 10)
Springer Verlag, Berlin, 1987
ISBM 0-387-13722-X (US)

where he discusses the Beneath-Beyond Method for d dimesions;
complexity: O (n log(n) + n^D) time and and O (n^D) space, where n
is the number of points and D = floor ((d + 1)/2). An O (n log(n))
Devide-and-Conquer algorithm which works for 3d only is also in there.

Another reference would be, eg,

Raimund Seidel
Constructing higher-dimensional convex hulls at log cost per face.
In Proc 18th Ann ACM Symp, 1986, p404--413.

Here at UIUC, we (Edelsbrunner's group) have also an implementation
of the Beneath-Beyond method.  Send me email, if interested.

--
Ernst Mucke,   Dept of Computer Science,  U of Illinois at Urbana-Champaign

--
--
Ernst Mucke,   Dept of Computer Science,  U of Illinois at Urbana-Champaign

### 3D convex hull algorithms

Quote:>I'm looking for references/implementations
>of 3D convex hull algorithms.  I'm familiar
>with 2D algorithms, but not 3D.  I'll
>appreciate any pointers.

Introduction to Computational Geometry, Preparata and Shamos, Springer-Verlag,
NY, 1985 describes a 3d hull algorithm.  A real-world implementation of the
algorithm in Preparata and Shamos is described by Day, A.M., "The Implementa-
tion of an Algorithm to Find the Convex Hull of a Set of Three-Dimensional
Points", ACM Transactions on Graphics, vol. 9, no. 1 (Jan. 1990), 105-132.

The latter paper is very interesting in that it shows that "[A]s is often the
case with geometric algorithms, the original publication tends to give a
rather concise strategic outline that emphasizes the complexity analysis but
glosses over implementation issues."

Roger House

### 3D convex hull algorithms

>>I'm looking for references/implementations
>>of 3D convex hull algorithms.  I'm familiar
>>with 2D algorithms, but not 3D.  I'll
>>appreciate any pointers.

>Introduction to Computational Geometry, Preparata and Shamos, Springer-Verlag,
>NY, 1985 describes a 3d hull algorithm.  A real-world implementation of the
>algorithm in Preparata and Shamos is described by Day, A.M., "The Implementa-
>tion of an Algorithm to Find the Convex Hull of a Set of Three-Dimensional
>Points", ACM Transactions on Graphics, vol. 9, no. 1 (Jan. 1990), 105-132.

>The latter paper is very interesting in that it shows that "[A]s is often the
>case with geometric algorithms, the original publication tends to give a
>rather concise strategic outline that emphasizes the complexity analysis but
>glosses over implementation issues."

introductory paragraph, and I quote.

'For example, experiment has revealed that this algorithm would
appear to have worst case complexity O(n^2) and not O(nlogn) as was
previously thought.'

This strikes me as a somewhat hesitant result.
=========================================================================
|                                       |===============================|

|                                       |===============================|
|       Imager                          |       (604) 228-2218          |
|       Department of Computer Science  |===============================|
|       University of British Columbia  |       Standard disclaimer     |
|       Vancouver, BC, Canada           |       included in this        |
|                                       |       box, right here.        |
=========================================================================

Does anybody know where I can get the source code/description for a 3D
convex hull algorithm which takes as input a number of floating point
coordinates of the points. All calculations must be in floats/double and
the output points should be in the same format. I have tried to
implement a number of algorithms including the incremental algorithm in
O'Rourke using doubles instead of ints but I end up getting all sorts of
errors!! It seems to me that all of the 3D convex hull algorithms that
exist only accept integer coordinates as input and avoid doubles/floats.

Can anybody help??

Thanks a lot