0

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.

fstab
  • 4,801
  • 8
  • 34
  • 66
  • This is probably better suited to http://programmers.stackexchange.com – jonrsharpe Aug 03 '14 at 20:20
  • 1
    Isn't *programmers* a stack exchange mostly for software engineering, design patterns and development practices, and quite off-topic with regards of algorithms for mathematical applications? – fstab Aug 03 '14 at 20:22
  • Yes, but I think it's better suited to "pre-coding" questions; SO tends to be for when you're implementing. Maybe look at the CompSci site? – jonrsharpe Aug 03 '14 at 20:24
  • Thanks! Just X-posted :) – fstab Aug 03 '14 at 20:35
  • possible duplicate of [robust algorithm for surface reconstruction from 3D point cloud?](http://stackoverflow.com/questions/838761/robust-algorithm-for-surface-reconstruction-from-3d-point-cloud) – Roland Smith Aug 04 '14 at 22:26

2 Answers2

3

Your task has a name, it's called Surface Reconstruction. Google it for details and overviews. If you use PCL then here is a good overview ending with code samples: http://www.pointclouds.org/assets/icra2012/surface.pdf

Another good library capable to deal with this task I know of is CGAL, see http://doc.cgal.org/latest/Surface_reconstruction_points_3/

datjko
  • 383
  • 1
  • 10
2

While I'm not an expert I think you need to calculate a convex hull on your point cloud first, and then do a Delaunay triangulation on the convex hull to get a wireframe. Scipy has provisions to calculate convex hulls and triangulations.

shiihs
  • 33
  • 5
  • 2
    Thinking back about what I wrote, I think the convex hull may conceal some of the detail in your data. Perhaps better find an expert :) – shiihs Aug 03 '14 at 20:40