# Is there an algorithm that, given a point cloud, infers an optimal wireframe (surface) structure?

I have a point cloud that I would like to convert to a surface, in the form of a wireframe lattice structure.

This means, from a sequence of 3D points (x,y,z), obtaining three 2D matrices X,Y,Z of the same size. In this way the points should be topologically related with a neighborhood of 4 (North, South, East, West). Such an organization of the points might, then, be plotted with functions such as matplotlib's Axes3D.plot_wireframe or Axes3D.plot_surface

From what I understood, the relationship of a point with the neighboring points is characterized by having minimal distance. I think that this is a combinatorial optimization problem, and NP-hard.

Now the question: are there algorithms that, given a list of 3D points, return the three aforementioned matrices X,Y,Z ?

Thank you very much. I also hope this is the correct stack exchange forum for this kind of question.

• What compatibility conditions do you impose on the directions? $\;$ – user6973 Aug 3 '14 at 21:32
• Hmm, I am not sure I understood your question... you mean optimization constraints? – fstab Aug 4 '14 at 10:29
• Can you explain/more precisely define a "wireframe lattice structure"? – usul Aug 4 '14 at 15:02
• What I mean with 'wireframe lattice structure' is just a grid, folded into a specific shape, for example, as representing the surface of an object. The nodes of this grid may well be the original points, with neighbourhood information attached. – fstab Aug 4 '14 at 15:15
• Does this "neighbourhood information" include specifying which of its four neighbors is, eg., its eastern neighbor? $\;$ – user6973 Aug 4 '14 at 17:43