title: Computing 2D contours from point cloud
body: <p>I have a 2D point cloud, each carrying some scalar value. Assume that this value can be interpolated at any point on plane, and I have a degree of freedom to choose the exact interpolation formula, as long as it's smooth, and converges to the given points when calculated in their proximity.
  My goal is to construct closed contours that correspond to constant scalar value.</p>
  
  <p>My specific case is somewhat more complex, but for simplicity let's assume that we have a terrain elevation (height) sampled at some points, and we need to construct contours of constant elevation, for some given values of it. Contours should be approximated by polylines.</p>
  
  <p>Previously I received the points in a form of a regular grid, and I solved it by examining and building (if necessary) contour segments in every grid cell separately. That is, for every grid cell I checked the values in corners to detect if the contour should cross cell boundaries (some corners should be higher and some lower), and calculated the intersection points respectively.</p>
  
  <p>Now I need to reconstruct this from arbitrary point cloud.</p>
  
  <p>Of course I can build a regular grid from the point cloud (since we know to interpolate), dense enough, from which the contours can be calculated, but I'd like a more efficient algorithm.
  My idea is to connect the points in the cloud so that the plane is covered by triangles (or more complex convex polygons), each would form a grid cell. Then I can construct contours pretty much like I did before.</p>
  
  <p>Is there a known algorithm to solve specifically this problem?</p>
  
  <p><strong>Update:</strong></p>
  
  <p>Thanks to @coproc. I'm aware of Delaunay triangulation, and this is probably the way to go.
  There are still questions however about how to interpolate in arbitrary point on a plane: would it be sufficient to consider only the triangle vertexes, or also other nearby points. In an unballanced case there may be a situation where a point is in extreme proximity to the triangle. For example here:
  <a href="https://i.stack.imgur.com/btAI9.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/btAI9.png" alt="For example here"></a></p>
  
  <p>As an alternative I can think of just starting from arbitrary point in a plane and then going perpendicular to the gradient to create the contours.</p>