有一个算法创建的三维点两个列表之间的网格，每个列表形成一个完整的循环？

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

示例图片

在链接图像的红点是所述第一组和蓝色是第二，灰色是连接两个集填充之间的间隙三角形的所需的输出。

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.

这图片显示了我想要做的正是在3D中，紫色的点构成的所述第一地形和其他点的轮廓形成在第二地形的孔的轮廓，该算法应创建一个目以填充内和外轮廓之间的间隙。

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.

推荐答案

您可以验证，如果下面的方法工作。的基本思想是，当你围绕内节点循环，将得到的外层一个上的最近的和添加的边缘。在外环最近应该是已经设置的一个，或它的邻居之一。所以，你可以利用这一点，像这样：

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