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

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

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

Introduction to Computational Geometry, Preparata and Shamos, Springer-Verlag,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.

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

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

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

3. :: A 3D Convex Hull Algorithm

6. Nikon LC-30 film/slide scanner?

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)

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

4 post • Page:**1** of **1**