Creating a mesh from scattered x,y,z points

AP (view profile)

on 16 Jun 2011

Hi,

How can I create a close or open surface which passes through some (x,y,z) points (scattered points)in space?

When I use mesh(x,y,z) MATLAB thinks that z is the value of a function at x and y.

x, y, and z are column vectors.

Products

No products are associated with this question.

Walter Roberson (view profile)

Answer by Walter Roberson

Walter Roberson (view profile)

on 16 Jun 2011

There is no unique solution unless you add a bunch of constraints.

Suppose you have the finite cloud of points and you create an arbitrary plane passing through the cloud. If you treat the points as infinitesimal and you choose the plane at random, the probability that the plane will exactly pass through any of the points approaches 0, so you should be able to easily find a plane that partitions the cloud in to two pieces. Now, generate your hypothetical surface following the "outside" of the cloud, but indenting far enough into the cloud to nearly cut it in half but then flowing out again along the "top" and "bottom" of the two partitions.

Now, there is nothing in the cloud that inherently disproves this indented surface as being "the right" surface. And there are a quite large number of different possible partitions of the cloud in to two subsets. You can't disprove it, and there are lots of ways it could happen. Especially if you let the indent be smaller and smaller until it is only "incorrectly" going in one or two points: whether any particular indentation is "incorrect" or not becomes completely arbitrary and undecidable.

Unless, that is, you impose some serious constraints.

===

I seem to recall that John d'Errico mentioned having done some work based upon convex hulls and alpha shapes.

John D'Errico

John D'Errico (view profile)

on 16 Jun 2011

I've got a general n-dimensional alpha shape code, but it is not always a good scheme for recovering a surface when the surface is not fully closed. (I did put together the beginnings of a tool based on a totally different idea, but it was only an outline, and lies unfinished as yet.) Anyway, in general I might look at established schemes like CRUST. Luigi Giacarri has done work on surface reconstruction from scattered data. I'd start there.

Join the 15-year community celebration.

Play games and win prizes!

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi