在三角网格中检测四面体？

Question

假设我有一个网格，其中的线连接顶点，以便将其分成四面体。是否有一种算法可以检测在给定顶点和线的情况下四面体的存在？（即，在给定具有连接线的网格的情况下，输出具有相同形状和体积的四面体集合。）

编辑：四面体不允许相交。

- Conner Ruhl

---

那么你的意思是说，形成四面体所需的所有边缘已经作为线集合存在了吗？ - Darren Engwirda

是的，边缘已经存在。 - Conner Ruhl

你的顶点和边是以什么形式存在的？ - meyumer

有一个顶点数组[x，y]和一条线数组[起点在顶点数组中的索引，终点在顶点数组中的索引]。 - Conner Ruhl

顶点是[x，y，z]对吧？我们不能在二维空间中讨论四面体。 - meyumer

抱歉，你是正确的，[x，y，z]。 - Conner Ruhl

Answer 1

我认为基于图形的方法可能有效。

首先，可以通过注意到边集定义了一个无向图G1(V1,E1)来恢复三角面片列表，以便在几何顶点之间建立连接。任何长度为3的循环都是该图中的三角形面片。

for (i = all vertices in G1)
// form list of vertex triplets
    list = find all length 3 cycles from ith vertex
// push new faces onto output
    for (j = all triplets in list)
        [v1,v2,v3] = list(j)
        if ([v1,v2,v3] is not an existing face)
            push triplet [v1,v2,v3] as a new face
        endif
    endfor
endfor

接下来，可以通过构建无向图 G2（V2，E2） 来恢复四面体，该图定义了面之间的连接性（即如果它们共享一个边，则这些面是相连的）。在此图中，任何长度为4的环都代表一个四面体。

for (i = all vertices in G2)
// form a list of face tuples
    list = find all length 4 cycles from ith vertex
// push new tetrahedra onto output
    for (j = all tuples in list)
        [f1,f2,f3] = list(j)
        [v1,v2,v3,v4] = unique vertices in faces [f1,f2,f3]
        if ([v1,v2,v3,v4] is not an existing tetrahedra)
            push tuple [v1,v2,v3,v4] as a new tetrahedra
        endif
    endif
endfor

希望这能有所帮助。

- Darren Engwirda