algorithm - 如何检测和保存边缘顶点的循环连通性(孔检测)？

Question

感谢您花时间阅读我的问题。

我正致力于检测三角形网格中的孔洞并用新的三角形填充它们。我已经完成了一些部分，以获得边顶点列表等。以下是形成孔的顶点/边，请看图片。

(9, 62)         => vertex # 9  and 62 makes an edge (left hole)
(66, 9)         => vertex # 66 and 9  makes an edge (left hole)
(70, 66)        => vertex # 70 and 66 makes an edge (left hole)
(62, 70)        => vertex # 62 and 70 makes an edge (left hole)

(147, 63)       => vertex # 147 and 63 makes an edge (right hole)
(55, 148)
(63, 149)
(149, 55)
(148, 147)

我需要做的第一件事是检查哪些顶点形成一个循环(意味着检测到一个洞)，然后保存在一组单独的循环顶点中。

问题是编写这样一个算法来检查给定的图(顶点/边)是否包含多少个循环？然后保存到单独的集合中。

请给我写一些简单的优化算法来解决这个问题。

谢谢。

Answer 1

1. 网格

   假设您的STL 网格得到了n您需要将其转换为索引格式的三角形。所以提取所有三角点并转换为两个单独的表。一个持有所有点，第二个持有每个三角形的 3 个点索引。假设你有 m点和n三角形。

   您应该从 O(n.m) 开始对点表(索引)进行排序并使用二进制搜索来加快速度至 O(m.log(n)) .

2. _edge结构

   创建包含网格所有边的结构。像这样的东西:

   struct _edge
    {
    int p0,p1; // used vertexes index
    int cnt;   // count of edge usage
    };
   

   哪里p0<p1 .

3. 创建 _edge edge[] table O(n)

   它应该是一个包含所有边的列表 (3n)，因此遍历所有三角形并为每个三角形添加 3 条边。计数设置为 cnt=1这是 O(n) .

   现在按 p0,p1 对列表进行排序这是 O(n.log(n)) .之后只需将所有边缘与相同的 p0,p1 连接起来即可。通过总结他们的 cnt并删除其中一个。如果编码正确，那么这是 O(n) .

4. 检测孔

   在常规 STL 中，每条边必须有 cnt=2 .如果cnt=1然后三角形不见了，你找到了你的洞。如果cnt>2你的网格有几何错误。

   所以用cnt>=2删除所有边来自你的 edge[]表格是O(n) .

5. 检测循环

   假设我们得到了 k在我们的 edge[] 中留下的边缘 table 。现在为共享一个点的每 2 条边创建三角形。像这样的东西:

   for (i=0;i<k;i++)
    for (j=i+1;j<k;j++)
     {
     if ((edge[i].p0==edge[j].p0)||(edge[i].p1==edge[j].p0)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p1);
     if ((edge[i].p0==edge[j].p1)||(edge[i].p1==edge[j].p1)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p0);
     }
   

   如果您对内部循环使用二进制搜索，那么这将是 O(k.log(k)) .此外，您应该避免添加重复的三角形并更正它们的缠绕，因此首先将三角形添加到单独的表格(或记住起始索引)，然后删除重复项(或者您可以直接在 add_triangle 中执行此操作)。

   还要处理更大的孔，不要忘记为您的 edge[] 添加新边 table 。您可以在处理当前边并重复 #4 后更新边，或者在运行时合并更改。

[Edit1] C++ 示例

最近我正在为这个 QA 编写一些 STL 代码:

• Generating outside supporters into mesh for 3D printing

因为我已经对所有基础设施进行了编码，所以我选择尝试一下，结果如下:

struct STL3D_edge
    {
    int p0,p1,cnt,dir;
    STL3D_edge()    {}
    STL3D_edge(STL3D_edge& a) { *this=a; }
    ~STL3D_edge()   {}
    STL3D_edge* operator = (const STL3D_edge *a) { *this=*a; return this; }
    //STL3D_edge* operator = (const STL3D_edge &a) { ...copy... return this; }
    int operator == (const STL3D_edge &a) { return ((p0==a.p0)&&(p1==a.p1)); }
    int operator != (const STL3D_edge &a) { return ((p0!=a.p0)||(p1!=a.p1)); }
    void ld(int a,int b) { cnt=1; if (a<=b) { dir=0; p0=a; p1=b; } else { dir=1; p0=b; p1=a; }}
    };
List<STL3D_edge> edge;
List<float> pnt;
void edge_draw()
    {
    int i; STL3D_edge *e;
    glBegin(GL_LINES);
    for (e=edge.dat,i=0;i<edge.num;i++,e++)
        {
        glVertex3fv(pnt.dat+e->p0);
        glVertex3fv(pnt.dat+e->p1);
        }
    glEnd();
    }
void STL3D::holes()
    {
    //  https://stackoverflow.com/a/45541861/2521214
    int i,j,i0,i1,i2,j0,j1,j2;
    float q[3];
    _fac        *f,ff;
    STL3D_edge  *e,ee,*e0,*e1,*e2;
    ff.attr=31<<5;                          // patched triangles color/id

    // create some holes for testing
    if (fac.num<100) return;
    for (i=0;i<10;i++) fac.del(Random(fac.num));

    // compute edge table
    edge.allocate(fac.num*3); edge.num=0;
    for (f=fac.dat,i=0;i<fac.num;i++,f++)
        {
        // add/find points to/in pnt[]
        for (i0=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[0]); if (vectorf_len2(q)<1e-6) { i0=j; break; }} if (i0<0) { i0=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[0][j]); }
        for (i1=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[1]); if (vectorf_len2(q)<1e-6) { i1=j; break; }} if (i1<0) { i1=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[1][j]); }
        for (i2=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[2]); if (vectorf_len2(q)<1e-6) { i2=j; break; }} if (i2<0) { i2=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[2][j]); }
        // add edges
        ee.ld(i0,i1); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
        ee.ld(i1,i2); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
        ee.ld(i2,i0); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
        }

    // delete even times used edges (to speed up the loops finding)
    for (i0=i1=0,e0=e1=edge.dat;i0<edge.num;i0++,e0++)
     if (int(e0->cnt&1)==1) { *e1=*e0; i1++; e1++; } edge.num=i1;
    // find 2 edges with one comon point (j1)
    for (e0=edge.dat,i0=0;i0<edge.num;i0++,e0++) if (int(e0->cnt&1)==1)
     for (e1=e0+1,i1=i0+1;i1<edge.num;i1++,e1++) if (int(e1->cnt&1)==1)
        {
        // decide which points to use
        j0=-1; j1=-1; j2=-1;
        if (e0->p0==e1->p0) { j0=e0->p1; j1=e0->p0; j2=e1->p1; }
        if (e0->p0==e1->p1) { j0=e0->p1; j1=e0->p0; j2=e1->p0; }
        if (e0->p1==e1->p0) { j0=e0->p0; j1=e0->p1; j2=e1->p1; }
        if (e0->p1==e1->p1) { j0=e0->p0; j1=e0->p1; j2=e1->p0; }
        if (j2<0) continue;
        // add missin triangle
        if (e0->dir)
            {
            vectorf_copy(ff.p[0],pnt.dat+j1);
            vectorf_copy(ff.p[1],pnt.dat+j0);
            vectorf_copy(ff.p[2],pnt.dat+j2);
            }
        else{
            vectorf_copy(ff.p[0],pnt.dat+j0);
            vectorf_copy(ff.p[1],pnt.dat+j1);
            vectorf_copy(ff.p[2],pnt.dat+j2);
            }
        ff.compute();
        fac.add(ff);
        // update edges
        e0->cnt++;
        e1->cnt++;
        ee.ld(j0,j2); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
        break;
        }
    }

STL3D 的完整 C++ 代码和描述类在上面的链接中。我使用了我在存档中找到的一些球体 STL 网格，并将孔修补三角形着色为绿色以识别它们。结果如下:

黑色线条是线框，红色线条只是 edge[],pnt[] 的调试图用于调试的数组 ...

如您所见，它甚至适用于比单个三角形还大的洞 :) ...