如何检测和保存边缘顶点的循环连通性（孔检测）？

Question

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

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

(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)

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

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

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

谢谢。

Answer 1

网格

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

您应该对点 table（索引）进行排序并使用二进制搜索将其从 O(n.m) 加速到 O(m.log(n))。

_edge结构

创建包含网格所有边的结构。类似于：

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

其中 p0<p1.

创建_edge edge[]tableO(n)

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

现在按 p0,p1 对列表进行排序，即 O(n.log(n))。之后，只需将所有具有相同 p0,p1 的边相加，将它们的 cnt 相加并删除其中之一即可。如果编码正确，那么这是 O(n).
检测孔

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

因此从 edge[] table 中删除所有带有 cnt>=2 的边，即 O(n).
检测循环

假设我们在 edge[] table 中还剩下 k 条边。现在为共享一个点的每 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))。另外，你应该避免添加重复的三角形并纠正它们的缠绕，所以首先添加三角形以分隔 table（或记住起始索引），然后删除重复项（或者你可以直接在 add_triangle 中进行） .

另外，要处理更大的孔，请不要忘记为您的 edge[] table 添加新边。您可以在处理当前边缘后更新边缘并重复 #4 或将更改合并到运行.

[Edit1] C++ 示例

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

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

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()
    {
    //  
    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 class 的完整 C++ 代码和说明在上面的 link 中。我使用了我在存档中找到的一些球体 STL 网格，并将孔修补三角形涂上绿色以识别它们。结果如下：

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

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

如何检测和保存边缘顶点的循环连通性（孔检测）？

How to detect and save cyclic connectivity in edge vertices (hole detection)?

algorithm

data-structures

graph-algorithm

stl-algorithm