Re: convex hull

• To: John Yao <johnyao@xxxxxxxx>
• Subject: Re: convex hull
• From: Bill Hibbard <billh@xxxxxxxxxxxxx>
• Date: Sun, 25 Aug 2002 17:03:37 -0500 (CDT)

Hi John,

The Watson and Clarkson algorithms included in VisAD for
finding Delaunay triangulations were also used by their
authors to find convex hulls.

I have never tried it, but you could probably apply either
visad/DelaunayWatson.java or visad/DelaunayClarkson.java
to find a tetrahedralization of your 3-D samples, then
look at its 'int[][] Walk' array to find faces that have
no adjacent tetrahedron. These faces should form the
convex hull of your data. Specifically, if Walk[i][j] = -1,
then triangular face j of tetrahedron i is part of the
convex hull.

Note this is just a theory off the top of my head, and
one that I have never tried. If anyone can correct me,
please do.

Cheers,
Bill
----------------------------------------------------------
Bill Hibbard, SSEC, 1225 W. Dayton St., Madison, WI  53706
hibbard@xxxxxxxxxxxxxxxxx  608-263-4427  fax: 608-263-6738
http://www.ssec.wisc.edu/~billh/vis.html


On Sun, 25 Aug 2002, John Yao wrote:

> Hello,
>
> I have generated some shapes using (DelaunayCustom(samples,tri)) from the
> Irregular3DSet.  However, the resulting geometry (surface covering) did not
> turn out the way we want it to be.  We are investigating a different
> algorithm called "convex hull"
> (http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html) to generate the
> surface based on the computed data points.
>
> I am just curious to know if VisAD happens to support this algorithm or
> method of creating the surface cover.  Thanks very much.
>
> john
>
>

• References:
  • convex hull
    • From: John Yao