I would like to triangulate a non-planar polygon (i.e. the vertices do not lie in the same 3D plane). The polygon consists of many points (hundreds). The triangulated surface does not have to be smooth. In fact, the denser it is, the better.
My initial ideas were:
I am not sure which of these ideas is applicable to my situation, or maybe there are even better ways?
More details: Even though the points on the contours are hundreds, they can be grouped in 3 to ~10 subsets, so that every subset closely approximates a line. The so-generated lines still don't lie in the same plane though. One can think about it as a flock of birds, which fly in a polygon, but not exactly on the same vertical height.
You might want to have a look at the Point Cloud Library. Amongst others, it can do surface reconstruction.