I've written a macro which produces the 3d convex hull of an arbitrary
point cloud using a 'beneath-beyond' type algorithm.
It grew out of a simple wish to triangulate the surface of a sphere for
use in a mechanics simulation. My first few attempts failed rather too
easily, so I read up on the problem and this came out of it.
It can get a bit slow - 500 co-spherical points takes about three and a
half minutes to parse on my 1GHz Athlon - and it probably scales at
something between O(n^2) and O(n^3) with the worst case being all points
on the hull.
The two images are:
200 co-spherical points giving a hull of all points, 594 edges and 396
400 points from VRand_In_Box() giving a hull of 55 points, 159 edges and
I'll post the files to p.b.s-f in a moment. Please let me know if anyone
finds them useful ...
Bye for now,
Post a reply to this message
Download 'convhull3.jpg' (31 KB)
Download 'convhull5.jpg' (26 KB)
Preview of image 'convhull3.jpg'
Preview of image 'convhull5.jpg'