Triangulation of the surface determined by sampling two of its cross-sections I have a data set that essentially looks like the picture below, i.e., it's given by sets of points in $\mathbb{R}^3$ that sample the cross-sections of a certain surface that in principle I do not know. In fact, I would like to recover this surface or, more precisely, a triangulation/mesh of it.

In this particular example, it is not difficult to see that we have a section of a cone. In this sense, I do not want to compute the convex hull of these points, but instead I just want to find its boundary (if this makes any sense; I actually don't know whether it does), i.e., I want to find the surface that one could obtain by simply joining the "corresponding" points in both "slices". (I've put "corresponding [points]" in quotes because I believe it's not straightforward to perform this matching exercise, i.e., find the point on the adjacent slice that isn't necessarily the closest one in the $\mathbb{R}^3$ metric, but would correspond to the closest one if we projected one slice into another and considered only the $\mathbb{R}^2$ distance between them, as seen below.)

 A: This is a problem that has been studied for a long time.
I showed with my students Carol Gitlin and Vinita Subramanian, that there does not always
exist a polyhedron that connects two arbitrary polygons in parallel slices.
In other words,
Daniel's hope to "simply [join] the 'corresponding' points in both 'slices' " cannot always
be realized:

C. Gitlin, J. O'Rourke, V. Subramanian.
  "On reconstruction of polyhedra from parallel slices,"
  International Journal of Computational Geometry & Applications, 6(1) 1996, 103-122.

These two polygons constitute a counterexample:

          
          


There is a very nice summary of the early work, and a practical algorithm, in:

Gill Barequet, Daniel Shapiro, Ayellet Tal.
  "History Consideration in Reconstructing Polyhedral Surfaces from Parallel Slices."
  Proceedings of IEEE Visualization, 1996. 
  (CiteSeer link)

Maybe look at this more recent work?:

Samir Akkouche, Eric Galin.
  "Implicit surface reconstruction from contours."
  The Visual Computer.
  August 2004, Volume 20, Issue 6, pp 392-401.
  (Springer link)


          


