c# - 如何连接两个平行的2d多边形以创建无缝的3d网格？

Question

假设我有两个多边形，一个在另一个上面，如下所示：
我想连接他们的顶点，创建一个三维网格周围的三角形。此图显示了一种方法（橙色线表示三角形边）：
这类事情可以由人凭直觉完成，但我真的很难把它转换成一个有效的算法。
多边形存储为List<Vector2>它们总是简单的，而且可能是凹的。

Answer 1

我想这样做：
在每个多边形中查找两个最近的点
这将用作起点
从这两个起点对顶点重新排序
具有相同的卷绕规则，例如图像上的CW-like
找到每个多边形的“中心”点
例如，所有顶点或边界框中点的平均值或其他值它不需要精确，但在复杂的凹形上，错误地选择中心位置会导致输出网格的误差。
为每个顶点添加角度信息
角度很容易使用

a=atan2(vertex-center)

在这一切之后，它应该是这样的：
角度[度]

index: 0   1   2   3   4
green: 355 085 135 170 230 
 blue: 020 135 255

现在你只需要从一个多边形到另一个多边形匹配两个最近的顶点
不要忘记角度差是max +/-180 deg并且如果使用弧度，则将常量 180,360转换为 PI,2.0*PI

da=ang1-ang0;
while (da<-180.0) da+=360.0;
while (da>+180.0) da-=360.0;
if (da<0.0) da=-da;

对于下一个文本 line(i,j)将意味着 i-th从绿色顶点和 j-th从蓝色多边形顶点
现在加入：
连接最近的顶点
只需处理所有绿色顶点并将它们连接到最近的蓝色顶点（图像上的黑色线条）

line(0,0)
line(1,1)
line(2,1)
line(3,1)
line(4,2)

把洞填满
网格三角剖分每个顶点至少需要2个关节，以便处理连接较少的点：

            index: 0 1 2 3 4
green connections: 1 1 1 1 1
 blue connections: 1 3 1

所以现在处理少于2次使用的蓝色顶点 (0,2)并将它们连接到最近的绿色顶点（图像上的黄色线）忽略已经使用的连接（在这种情况下选择下一个）

line(1,0)
line(3,2)

所以：

            index: 0 1 2 3 4
green connections: 1 2 1 2 1
 blue connections: 2 3 2

现在处理剩下的绿色不到2次使用的顶点连接到不到3次使用的蓝色顶点。如果连接少于3个，则只选择下一个已用连接点；如果连接多于1个，则使用最近的连接点（图像上的红线）。
line(0,2)绿色0连接到蓝色0，因此从蓝色1,2中选择（1也用于SO 2）
line(2,-)绿色2连接到蓝色1，蓝色1使用了3次，因此忽略此顶点
line(4,-)绿色4连接到蓝色2，蓝色2使用了3次，因此忽略此顶点

                index: 0 1 2 3 4
    green connections: 2 2 1 2 1
     blue connections: 2 3 3

仅此而已现在你应该这样做：
[注]
也可以使用周长位置/周长而不是角度（有时效果更好）
凹多边形会把这搞得一团糟，所以应该添加一些三角形相交检查，以避免出现问题。
另外，多边形之间的顶点数量不应该相差太大，在这种情况下，您仍然可以分割一些线以添加缺少的点，否则3倍的使用条件将是错误的（如果顶点数相差2倍或更多倍）
如果你想安全的话，你应该把多边形切割成凸出的部分，然后把它们分开，并且只有在这之后才能把网格连接起来。
[编辑1]新方法不易受到凹面和点密度的影响
它的速度较慢，但看起来它在寻找更复杂的形状作为例子，我从评论中选择了修改后的星号和加号。
在每个多边形中查找两个最近的点
这将用作起点
从这两个起点对顶点重新排序
具有相同的卷绕规则，例如图像上的CW-like
准备边缘列表
我们需要一个结构来保持多边形之间的所有连接。我决定这样做：

List< List<int> > edg0,edg1;

其中 edg0[point0][i]保持连接到0点的 i-th point1请注意，在代码数组中index是point index，而数组的实际值n是全局point table pnt中的point index，在这里我可以在这两者之间进行如下转换：

point0 = (pnt_index - ix0)/3 
point1 = (pnt_index - ix1)/3 
pnt_index = ix0 + 3*point0
pnt_index = ix1 + 3*point1

其中 ix0,ix1是 pnt中每个多边形的开始索引。
连接闭合点
我添加了阈值，因此点距离必须小于threshold minll，而不是连接到最近的点此阈值是两个起点距离（最小距离）的倍数。代码中：

minll=2.5*l0;

但请注意，我比较的是 distance^2的速度，所以如果你有距离的话

minl=sqrt(2.5)*l0;

乘法系数可以调整。。。

如你所见，恒星上的远点由于阈值而没有连接。
在第0点填充未使用的孔
只需找到未使用的点的序列0，然后使用连接的第一个邻居从头到尾插入连接。因此，如果点0 i0 .. i1未连接且其最近的邻居已连接，则取其最近的连接点1 j0 .. j1，并简单地将点 i与 j线性连接，其中：

i = i0 + t*(i1-i0)
j = j0 + t*(j1-j0)

其中 t是通过所有“整数”点索引的参数 t=<0.0,1.0>（使用DDA）。

在点1中填充未使用的孔
它与#5相同，但在另一个多边形中查找未连接的点1。

查找并连接单条连接线
两个端点只使用一次所以只要找到这样的边并将其连接到相邻的点。

找到形成四孔的奇异点并将其三角化
因此，找到只连接了一次的 poinst0，然后测试它的邻居是否连接回了第一个连接到的 point0。如果没有，你就把它三角化。

现在只需从 point1
直线很简单，因为它们已经直接编码，对于三角形，只需搜索相邻的 edg0,edg1就可以找到与同一 point0的连接。如果发现形成三角形。三角形也应在“其他边”列表中形成，以便搜索连接到同一个 point1的相邻 point1。
这里是GL/C++的例子

List<double> pnt;
List<int> lin,tri;
int iy0=0,iy1=0,iy2=0,iy3=0;// pol0<iy0,iy1),pol1<iy1,iy2),merge<iy2,iy3)
int ix0=0,ix1=0,ix2=0;      // points1<ix0,ix1), points2<ix1,ix2)
//---------------------------------------------------------------------------
void obj_init()
    {
    // input data
    const double d=0.5;             // distance between polygons
    const double pol0[]={0.0,2.0, 1.0,2.0, 1.0,3.0, 2.00,3.0, 2.0,2.0, 3.00,2.0, 3.0,1.0, 2.0,1.0, 2.0,0.0, 1.0,0.0, 1.0,1.0, 0.0,1.0, 0.0,2.0};
//  const double pol1[]={0.0,0.0, 1.0,1.0, 0.0,2.0, 1.25,1.5, 1.5,2.5, 1.75,1.5, 3.0,2.0, 2.0,1.0, 3.0,0.0, 1.5,0.7};
    const double pol1[]={0.0,0.0, 1.0,1.0, 0.0,2.0, 1.25,1.5, 1.5,5.0, 1.75,1.5, 3.0,2.0, 2.0,1.0, 3.0,0.0, 1.5,0.7};
//                                                                ***
    // variables
    List<double> tmp;
    List< List<int> > edg0,edg1;    // edge table

    double minll;                   // max distance to points that will join automatically
    double p[3],l0,l;
    int i,i0,i1,ii,ii0,ii1,di;
    int j,j0,j1,jj,jj0,jj1,dj;
    int k,n0,n1,e,de;
    pnt.num=0;
    lin.num=0;

    // copy pol0 to point list pnt[]
    ix0=pnt.num;
    n0=sizeof(pol0)/sizeof(pol0[0]);
    for (j=pnt.num,i=0;i<n0;)
        {
        pnt.add(pol0[i]); i++;
        pnt.add(pol0[i]); i++;
        pnt.add(-d);
        } ix1=pnt.num; n0/=2;

    // copy pol1 to point list pnt[]
    n1=sizeof(pol1)/sizeof(pol1[0]);
    for (j=pnt.num,i=0;i<n1;)
        {
        pnt.add(pol1[i]); i++;
        pnt.add(pol1[i]); i++;
        pnt.add(+d);
        } ix2=pnt.num; n1/=2;

    // add polygon edges
    iy0=lin.num;
    for (j=ix1-3,i=ix0;i<ix1;j=i,i+=3){ lin.add(j); lin.add(i); } iy1=lin.num;
    for (j=ix2-3,i=ix1;i<ix2;j=i,i+=3){ lin.add(j); lin.add(i); } iy2=lin.num;

    // find closest points -> start points i0,j0
    i0=-1; j0=-1; l0=0.0; minll=0.0;
    for (i=ix0;i<ix1;i+=3)
     for (j=ix1;j<ix2;j+=3)
        {
        vector_sub(p,pnt.dat+i,pnt.dat+j);
        l=vector_len2(p);
        if ((i0<0)||(l<l0)){ l0=l; i0=i; j0=j; }
        } minll=2.5*l0;
    // reorder points so closest ones are first
    if (i0!=ix0)
        {
        tmp.num=0;  for (i=ix0;i<ix1;i++) tmp.add(pnt.dat[i]);                          // copy to temp
        for (j=i0,i=ix0;i<ix1;i++,j++,(j>=ix1)?j=ix0:j=j) pnt.dat[i]=tmp.dat[j-ix0];    // reorder
        }
    if (j0!=ix1)
        {
        tmp.num=0;  for (i=ix1;i<ix2;i++) tmp.add(pnt.dat[i]);                          // copy to temp
        for (j=j0,i=ix1;i<ix2;i++,j++,(j>=ix2)?j=ix1:j=j) pnt.dat[i]=tmp.dat[j-ix1];    // reorder
        }

    // init edge lists
    edg0.allocate(n0); edg0.num=n0; for (i=0;i<n0;i++) edg0[i].num=0;
    edg1.allocate(n1); edg1.num=n1; for (i=0;i<n1;i++) edg1[i].num=0;

    // join close points
    for (ii=0,i=ix0;i<ix1;i+=3,ii++)
        {
        j0=-1; jj0=-1; l0=0.0;
        for (jj=0,j=ix1;j<ix2;j+=3,jj++)
            {
            vector_sub(p,pnt.dat+i,pnt.dat+j);
            l=vector_len2(p);
            if ((j0<0)||(l<l0)){ l0=l; j0=j; jj0=jj; }
            }
        if ((j0>=0)&&(l0<minll))
            {
            edg0.dat[ii ].add(j0);
            edg1.dat[jj0].add(i);
            }
        }

    // fill unused holes in points0
    for (e=1,i=0;e;)
        {
        e=0;
        // find last used point0 -> i0
        i0=-1; i1=-1;
        for (j=0;j<n0;j++,i++,(i==n0)?i=0:i=i) if (edg0.dat[i].num) i0=i; else if (i0>=0) break;
        // find next used point0 -> i1
        if (i0>=0) if (edg0.dat[i].num==0)
         for (j=0;j<n0;j++,i++,(i==n0)?i=0:i=i) if (edg0.dat[i].num){ i1=i; break; }
        if (i1>=0)
            {
            // find last used point1 joined to i0 -> j0
            j0=-1; jj0=-1; l0=0.0;
            i=i0+1; if (i>=n0) i=0; ii=ix0+i+i+i;
            for (j=0;j<edg0.dat[i0].num;j++)
                {
                jj=edg0.dat[i0].dat[j];
                vector_sub(p,pnt.dat+ii,pnt.dat+jj);
                l=vector_len2(p);
                if ((j0<0)||(l<l0)){ l0=l; j0=(jj-ix1)/3; jj0=jj; }
                } i0=i;
            // find next used point1 joined to i1 -> j1
            j1=-1; jj1=-1; l0=0.0;
            i=i1-1; if (i<0) i=n0-1; ii=ix0+i+i+i;
            for (j=0;j<edg0.dat[i1].num;j++)
                {
                jj=edg0.dat[i1].dat[j];
                vector_sub(p,pnt.dat+ii,pnt.dat+jj);
                l=vector_len2(p);
                if ((j1<0)||(l<l0)){ l0=l; j1=(jj-ix1)/3; jj1=jj; }
                } i1=i;
            // join i0..i1 <-> j0..j1
            di=i1-i0; if (di<0) di+=n0; // point0 to join
            dj=j1-j0; if (dj<0) dj+=n1; // point1 to join
            de=di; if (de<dj) de=dj;    // max(points0,point1)
            for (e=0;e<=de;e++)
                {
                i=i0+((e*di)/de); if (i>=n0) i-=n0; ii=ix0+i+i+i;
                j=j0+((e*di)/de); if (j>=n1) j-=n1; jj=ix1+j+j+j;
                for (k=0;k<edg0.dat[i].num;k++) // avoid duplicate edges
                 if (edg0.dat[i].dat[k]==jj)
                  { k=-1; break; }
                if (k>=0)
                    {
                    edg0.dat[i].add(jj);
                    edg1.dat[j].add(ii);
                    }
                }
            e=1;
            }
        }

    // fill unused holes in points1
    for (e=1,i=0;e;)
        {
        e=0;
        // find last used point1 -> i0
        i0=-1; i1=-1;
        for (j=0;j<n1;j++,i++,(i==n1)?i=0:i=i) if (edg1.dat[i].num) i0=i; else if (i0>=0) break;
        // find next used point1 -> i1
        if (i0>=0) if (edg1.dat[i].num==0)
         for (j=0;j<n1;j++,i++,(i==n1)?i=0:i=i) if (edg1.dat[i].num){ i1=i; break; }
        if (i1>=0)
            {
            // find last used point0 joined to i0 -> j0
            j0=-1; jj0=-1; l0=0.0;
            i=i0+1; if (i>=n1) i=0; ii=ix1+i+i+i;
            for (j=0;j<edg1.dat[i0].num;j++)
                {
                jj=edg1.dat[i0].dat[j];
                vector_sub(p,pnt.dat+ii,pnt.dat+jj);
                l=vector_len2(p);
                if ((j0<0)||(l<l0)){ l0=l; j0=(jj-ix0)/3; jj0=jj; }
                } i0=i;
            // find next used point0 joined to i1 -> j1
            j1=-1; jj1=-1; l0=0.0;
            i=i1-1; if (i<0) i=n1-1; ii=ix1+i+i+i;
            for (j=0;j<edg1.dat[i1].num;j++)
                {
                jj=edg1.dat[i1].dat[j];
                vector_sub(p,pnt.dat+ii,pnt.dat+jj);
                l=vector_len2(p);
                if ((j1<0)||(l<l0)){ l0=l; j1=(jj-ix0)/3; jj1=jj; }
                } i1=i;
            // join i0..i1 <-> j0..j1
            di=i1-i0; if (di<0) di+=n1; // point1 to join
            dj=j1-j0; if (dj<0) dj+=n0; // point0 to join
            de=di; if (de<dj) de=dj;    // max(points0,point1)
            for (e=0;e<=de;e++)
                {
                i=i0+((e*di)/de); if (i>=n1) i-=n1; ii=ix1+i+i+i;
                j=j0+((e*di)/de); if (j>=n0) j-=n0; jj=ix0+j+j+j;
                for (k=0;k<edg1.dat[i].num;k++) // avoid duplicate edges
                 if (edg1.dat[i].dat[k]==jj)
                  { k=-1; break; }
                if (k>=0)
                    {
                    edg1.dat[i].add(jj);
                    edg0.dat[j].add(ii);
                    }
                }
            e=1;
            }
        }

    // find&connect singular connection lines (both endpoints are used just once)
    for (i=0;i<n0;i++)
     if (edg0.dat[i].num==1)    // point0 used once
        {
        jj=edg0.dat[i].dat[0];  // connected to
        j=(jj-ix1)/3;
        if (edg1.dat[j].num==1) // point1 used once
            {
            i0=i-1; if (i<  0) i+=n0;   // point0 neighbors
            i1=i+1; if (i>=n0) i-=n0;
            ii =ix0+i +i +i;
            ii0=ix0+i0+i0+i0;
            ii1=ix0+i1+i1+i1;
            if (edg1.dat[j].dat[0]!=ii0)    // avoid duplicate edges
                {
                edg1.dat[j].add(ii0);
                edg0.dat[i0].add(jj);
                }
            if (edg1.dat[j].dat[0]!=ii1)    // avoid duplicate edges
                {
                edg1.dat[j].add(ii1);
                edg0.dat[i1].add(jj);
                }
            }
        }

    // find singular poinst0 that form QUAD hole and triangulate it
    for (i=0;i<n0;i++)
     if (edg0.dat[i].num==1)    // point0 used once
        {
        jj=edg0.dat[i].dat[0];  // connected to
        j=(jj-ix1)/3;
        i0=i-1; if (i<  0) i+=n0;   // point0 neighbors
        i1=i+1; if (i>=n0) i-=n0;
        j0=j-1; if (j<  0) j+=n1;   // point1 neighbors
        j1=j+1; if (j>=n1) j-=n1;
        ii =ix0+i +i +i;
        ii0=ix0+i0+i0+i0;
        ii1=ix0+i1+i1+i1;
        jj0=ix1+j0+j0+j0;
        jj1=ix1+j1+j1+j1;
        for (k=0;k<edg1.dat[j].num;k++) // avoid duplicate edges
            {
            if (edg1.dat[j].dat[k]==ii0) i0=-1;
            if (edg1.dat[j].dat[k]==ii1) i1=-1;
            }
        if (i0>=0)
            {
            edg1.dat[j ].add(ii0);
            edg0.dat[i0].add(jj );
            }
        if (i1>=0)
            {
            edg1.dat[j ].add(ii1);
            edg0.dat[i1].add(jj );
            }
        }

    // extract merge triangles from edge0
    for (i0=0,i1=1;i0<n0;i0++,i1++,(i1>=n0)?i1=0:i1=i1)
        {
        ii0=ix0+i0+i0+i0;
        ii1=ix0+i1+i1+i1;
        // find point1 joined to both points0 i0,i1
        for (i=0;i<edg0.dat[i0].num;i++)
         for (j=0;j<edg0.dat[i1].num;j++)
          if (edg0.dat[i0].dat[i]==edg0.dat[i1].dat[j])
            {
            jj=edg0.dat[i0].dat[i];
            tri.add(ii0);
            tri.add(ii1);
            tri.add(jj);
            }
        }
    // extract merge triangles from edge1
    for (i0=0,i1=1;i0<n1;i0++,i1++,(i1>=n1)?i1=0:i1=i1)
        {
        ii0=ix1+i0+i0+i0;
        ii1=ix1+i1+i1+i1;
        // find point1 joined to both points0 i0,i1
        for (i=0;i<edg1.dat[i0].num;i++)
         for (j=0;j<edg1.dat[i1].num;j++)
          if (edg1.dat[i0].dat[i]==edg1.dat[i1].dat[j])
            {
            jj=edg1.dat[i0].dat[i];
            tri.add(ii0);
            tri.add(ii1);
            tri.add(jj);
            }
        }

    // extract merge edges
    for (i=ix0,ii=0;ii<n0;ii++,i+=3)
     for (j=0;j<edg0.dat[ii].num;j++)
        {
        lin.add(i);
        lin.add(edg0.dat[ii].dat[j]);
        }
    iy3=lin.num;

/*
    // [debug]
    AnsiString txt="";
    for (txt+="[edg0]\r\n",i=0;i<n0;i++,txt+="\r\n")
     for (txt+=AnsiString().sprintf("%2i:",i),j=0;j<edg0.dat[i].num;j++)
      txt+=AnsiString().sprintf("%2i ",(edg0.dat[i].dat[j]-ix1)/3);
    for (txt+="\r\n[edg1]\r\n",i=0;i<n1;i++,txt+="\r\n")
     for (txt+=AnsiString().sprintf("%2i:",i),j=0;j<edg1.dat[i].num;j++)
      txt+=AnsiString().sprintf("%2i ",(edg1.dat[i].dat[j]-ix0)/3);
    e=FileCreate("debug.txt");
    FileWrite(e,txt.c_str(),txt.Length());
    FileClose(e);
*/
    }
//---------------------------------------------------------------------------
void obj_draw()
    {
    int i,j;
    glLineWidth(2.0);
    glColor3f(0.1,0.1,0.1); glBegin(GL_LINES); for (i=0;(i<iy0)&&(i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // aux
    glColor3f(0.1,0.1,0.9); glBegin(GL_LINES); for (   ;(i<iy1)&&(i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // polygon 0
    glColor3f(0.9,0.1,0.1); glBegin(GL_LINES); for (   ;(i<iy2)&&(i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // polygon 1
    glColor3f(0.1,0.9,0.1); glBegin(GL_LINES); for (   ;(i<iy3)&&(i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // merge
    glColor3f(0.1,0.1,0.1); glBegin(GL_LINES); for (   ;         (i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // aux
    glLineWidth(1.0);

    glPointSize(5.0);
    glColor3f(0.9,0.9,0.1); glBegin(GL_POINTS); glVertex3dv(pnt.dat+ix0+0); glVertex3dv(pnt.dat+ix1+0); glEnd();    // 1st points
    glColor3f(0.1,0.9,0.9); glBegin(GL_POINTS); glVertex3dv(pnt.dat+ix0+3); glVertex3dv(pnt.dat+ix1+3); glEnd();    // 2nd points
    glColor3f(0.3,0.3,0.3); glBegin(GL_POINTS); for (i=0;i<pnt.num;i+=3) glVertex3dv(pnt.dat+i); glEnd();           // points
    glPointSize(1.0);

    glDisable(GL_CULL_FACE);
    glColor3f(0.2,0.2,0.2); glBegin(GL_TRIANGLES); for (i=0;i<tri.num;i++) glVertex3dv(pnt.dat+tri.dat[i]); glEnd();    // faces
    }
//---------------------------------------------------------------------------

我还使用我的动态列表模板，以便：
point0与 List<double> xxx;相同
double xxx[];将 xxx.add(5);添加到列表末尾
5访问数组元素（安全）
xxx[7]访问数组元素（不安全但快速的直接访问）
xxx.dat[7]是数组的实际使用大小
xxx.num清除数组并设置 xxx.reset()
xxx.num=0为 xxx.allocate(100)项预先分配空间