How to construct a mesh from given edge points?

I have some points on the edge(left image), and I want to construct a mesh(right), Is there any good algorithm to achieve it? many thanks!

开发者_C百科

image can see here http://ww3.sinaimg.cn/large/6a2c8e2bjw1dk8jr3t7eaj.jpg

---

To begin with, see Delauney triangulation. Look at this project: http://people.sc.fsu.edu/~jburkardt/c_src/triangulate/triangulate.html.

Edited because my original had too few details on edge-flipping, and when I tried to provided those details I found the TRIANGULATE project.

---

If the region is flat or quasi-flat look for Ear Clipping approach (http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf). In the case of curved surface you need point inside the region and therefore you may need Constrained Delaunay Triangulation (otherwise some edges may not be included in the triangulation).

---

There is delaunayn function in geometry package for R language (see doc) It takes an array of boundary points (as in your case) to create a Delaunay mesh on it.

You could also save your geometry into some well-known format, and use one of mesh generators.