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

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?

-
Very interesting problem. Using ListSurfacePlot3D with the right subset of points would do the graphic part. Getting that subset is the hard part. –  FJRA Mar 15 '12 at 2:03
Please post both pointsets (as shown in your edit) somewhere in the 'net. –  belisarius Mar 17 '12 at 2:22
I see you placed a bounty on this. As belisarius said, you should post the point set, otherwise we can't test. Export to WDX and upload somewhere. –  Szabolcs Mar 17 '12 at 15:38
How do you define the surface? Do you mean the convex hull or something else? And what is a uniform shape? –  Sjoerd C. de Vries Mar 17 '12 at 16:07
+1 just for the sweet 2D splines –  Reb.Cabin Mar 20 '12 at 12:22

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]]

-
@RHall Yep. But I am not aware of a way for using BSplineSurface[] as an interpolation (there is one out there ... for sure) –  belisarius Mar 15 '12 at 2:14
What's your version of Mathematica? I cannot run it without the edit I did. –  FJRA Mar 15 '12 at 7:12
With Graphics3D[GraphicsComplex[data3D, Polygon[surface[[2]]]]] I can run it too. TetGenConvexHull returns me to vectors, the points and the surface polygons. –  FJRA Mar 15 '12 at 7:14
@belisarius The documentation uses a slightly different syntax: see TetGenLink/ref/TetGenConvexHull: {pts, surface} = TetGenConvexHull[data3D]; Graphics3D[ GraphicsComplex[pts, Polygon[surface]]] Your syntax gives me a lot of jumbled polygons. –  Yves Klett Mar 15 '12 at 8:37
belisarius: I believe you have 8.0.0. Maybe this is another case of functionality changing between minor versions. In 8.0.4, TetGenConvexHull` returns a list with two elements: the point coordinates and the point indices defining the surface polygons. It looks like, your version only returns the latter. So for me to be able to run it, @FJRA's edit is necessary. You could add a note to the answer about this problem. I think TetGenLink is primarily for internal use ... perhaps that's why it changed. –  Szabolcs Mar 15 '12 at 8:59