在三角网中检测四面体？

Question

假设我有一个网格,其中的线条连接顶点的方式可以将其拆分为四面体.是否有一个算法可以用来检测给定顶点和线条的四面体的存在？(即,如果网格带有连接线,则输出一组具有相同形状和体积的四面体.)

编辑:不允许四面体交叉.

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

希望这可以帮助。