3D convex hull algorithms

3D convex hull algorithms

Post by Larry Bergm » Sat, 15 Sep 1990 04:31:24



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

Post by Ernst P Muc » Sat, 15 Sep 1990 07:59:35


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

Post by Roger Hou » Wed, 19 Sep 1990 04:36:45



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

Post by John Buchan » Thu, 20 Sep 1990 01:09:59




>>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."

The flavor of this article is best described by a sentence from the
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.        |
=========================================================================

 
 
 

1. 3D convex hull algorithms

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

2. Anyone want to trade Quicktime Movies? esp funny TV Commercials?

3. :: A 3D Convex Hull Algorithm

4. Form.PrintForm Help

5. 3D convex-hull algorithm

6. Nikon LC-30 film/slide scanner?

7. 3D convex hull Algorithm

8. New 3D Site

9. Help :: 3D Convex Hull Algorithm

10. Algorithm for construction of Vornoi polygon and 3D convex hull

11. convex hull for convex polygons (3D)

12. Convex Hull Algorithm

13. A. M. Day's Convex Hull Algorithm