# comp.graphics.algorithms

## Subject: Re: Bounding a set of points with a curve?

"Boxman" wrote in message
> I have a dense set of 3d points (for example 10000) that lie on a
> defined surface but don't necessarily cover the whole surface. The
> points are not regularly spaced and the shape that they cover on the
> surface is irregular. I would like to draw a polyline connecting only
> the points that form the boundary that encloses all of these points.

(1) When you say the points "lie on a defined surface", do you
know what that surface is? If you do and the surface is
parameterized, you can construct a "boundary" curve in the
parameter domain. If it is not parameterized, you might be able
to find a parameterization (analytically or, perhaps, numerically
using conformal maps). If you do not know the surface, see (2).

(2) Is your surface the graph of a function in *some* coordinate
system? If so, you can project the points to a plane and use
a convex hull (or alpha hull) algorithm to locate the boundary
points.

more concrete suggestions.

--
Dave Eberly
http://www.geometrictools.com