Algorthim to create a mesh between two sets of points

Question

Is there an algorithm to create a mesh between two lists of 3D points, each list forms a full loop?

Example Image

In the linked image the Red dots are the first set and the blue are the second, the grey is the desired output of triangles connecting the two sets filling the gap between.

This image shows what I would like to do exactly in 3d , The purple points form the outline of the first terrain and the other points forms the outline of a hole in the second terrain, the algorithm should create a mesh to fill the gap between the inner and outer outline.

Answer 1

Can you verify if the following method works. The basic idea is, as you loop around the inner nodes, you get the nearest from the outer one and add an edge. The nearest on the outer loop should be either the one already set, or one of its neighbours. So you can exploit this, like so:

innernode = firstnode(innerloop)
outernode = NULL

while(innernode) do

    if(outernode) then
        //For every new node, check if the outer node is the nearest, 
        //or if any of its neighbours are
        newouternode = find_nearest_among(outernode, prev(outernode), 
                                            next(outernode), innernode)
        if(newouternode != outernode) then
            //If we found a new node, add an extra edge, 
            //otherwise, we'll have quads
            //The figure shows why this is needed.
            make_edge(innernode, outernode)
            outernode = newouternode 
        end
    else
        //the first time, find the closest node in the outer loop)
        outernode = find_nearest(outerloop, innernode)
    end
    //continue making an edge to the outernode, we're closest to
    make_edge(innernode, outernode)

    //move on
    innernode = next(innernode)
end

Answer 2

Input are two loops of points, such that one loop is in inside other loop.

Idea is to connect points by traversing loops in same direction (parallel.) Find one point in outer and one point in inner loop such that segment connecting them doesn't intersect any loop. There are two possibilities to move to next segment, move point on inner loop or move point on outer loop. Test these two segments for intersection with loops, and (if needed) quality of triangle produced by last segment and next segment, and decide next segment to use. Repeat moving segment until whole points return to initial segment.