How can the {x,y,z} points that fall on the outer boundary of a set of values be selected and smoothly surfaced?

Question

For a given set of x,y,z values, that may, or may not form a uniform shape, how can the center of the data cloud be found, and the surface points be located and a solid smooth surface created from them? In some cases a set of points may create intersections of shapes but there are no holes to deal with in the data.

x=RandomReal[1,{400,3}];

ListPointPlot3D[x]

here's a 2D version of a bSpline interpolation function I have used for joining the surface points smoothly after dividing them in painful ways. Running Mathematica 8.04

ParameterAverageKnots[deg_, data_] := 
 Module[{param = data[[All, 1]]}, 
  Join[ConstantArray[param[[1]], deg + 1], 
   Table[1/deg Sum[param[[i]], {i, j, j + deg - 1}], {j, 2, 
     Length[param] - deg}], ConstantArray[param[[-1]], deg + 1]]]

UniformKnots[deg_, data_] := 
 Rescale[Join[ConstantArray[0, deg], 
   Range[0, 1, 1/(Length[data] - deg)], ConstantArray[1, deg]], {0, 
   1}, {data[[1, 1]], data[[-1, 1]]}]

UnclampedKnots[deg_, data_] := 
 Rescale[Range[Length[data] + deg + 1], {deg + 1, 
   Length[data] + 1}, {data[[1, 1]], data[[-1, 1]]}]

BasisMatrix[deg_, data_, knotfunc_] := 
 With[{knots = knotfunc[deg, data]}, 
  Table[BSplineBasis[{deg, knots}, j - 1, data[[i, 1]]], {i, 
    Length[data]}, {j, Length[data]}]]             

BSplineInterpolation2D[data_, deg_, knotfunc_] := 
  Module[{knots, m, sol},
   knots = knotfunc[deg, data];
   m = BasisMatrix[deg, data, knotfunc];
   sol = LinearSolve[m, data[[All, 2]]];
   BSplineFunction[sol, 1, SplineDegree -> deg, SplineKnots -> knots]];

degree = 3;
pts = RandomReal[5, 10] // Sort
data = Transpose[{Range[10], pts}]
f = BSplineInterpolation2D[data, degree, UniformKnots]
Plot[f[t], {t, 1, 10}, Epilog -> {Red, Point@data}]

can it be extended to this purpose? Of course there's still that tough part about getting the outer points to surface, and after splining how to surface the form.

To review this issue again after all of the great input and trials, the results show that for some very similar shapes the solution did not work. Here are 2 examples:

Now for slightly changed data with a similar shape:

In both of these examples the data points provide very reasonable shapes to surface. One works, the other fails... thoughts?

The failed test data can be downloaded here.

Answer 1

Not sure about the creation of a "smooth" surface. But from Mma help, you may create a convex hull in 3D by using TetGenConvexHull

Needs["TetGenLink`"]
data3D = RandomReal[{0, 1}, {100, 3}];
Graphics3D[Point[data3D]];
surface = TetGenConvexHull[data3D];
(* TetGenConvexHull was changed sometime between 8.0.0 and 8.0.4.
   Uncomment the following line only if you are using 8.0.4. *)
(* surface = Last[surface] *)
Graphics3D[GraphicsComplex[data3D, Polygon[surface]]]

HTH ... I am not really sure ...

To get the points in the convex hull, you could use for example:

  pointss = data3D[[Union@Flatten@surface]]

Answer 2

If what you want is a nice smooth surface of the outer boundary, then in Mathematica 10.2 you can do the following:

data3D = RandomReal[{0, 1}, {100, 3}];  (* generate some random point *)
cvx = ConvexHullMesh[data3D]            (* get the outer boundary *)

Now we can Discretize the surface and smooth it in one go:

smooth = DiscretizeRegion[cvx,  MeshCellStyle -> {{1, All} -> RGBColor[1/2, 0, 0],      
                 {2, All} -> RGBColor[1/2, 0, 0]}, PlotTheme -> "SmoothShading"]

OR without the triangles:

You can recover the surface points from MeshCoordinates[smooth]