Answer
5—Extending
the 2-D convex hull to 3-D is a bit tricky because the
search must be in two dimensions instead of one.
One
way to approach it is to:
·
Find the lowest point.
·
Find the lowest-slope edge to one other point.
· Using
that edge, find the lowest-slope plane to a third point.
These three points define
one facet of the convex hull.
· Continue
searching in a circular manner around point 1, using it
and point 3 to define the next edge. Keep track of the
facets that you find so that you know if you come across
the same one a second time.
· When
you get back to point 2, use the edges between 2 and 3,
3 and 4, etc. to find additional facets until all of the
exterior facets of the polyhedron have been identified.
Contributor: David Tweed
Published
February 2004
