Wykryj czworościany w obrębie trójkątnej siatki?

Question

Załóżmy, że mam siatkę, która ma linie łączące wierzchołki w sposób, który umożliwi podział na czworościany. Czy istnieje algorytm, za pomocą którego mogę wykryć obecność czworościanów, biorąc pod uwagę wierzchołki i linie? (Tj., Biorąc pod uwagę siatkę z liniami łączącymi, wyprowadzić zestaw czworościanów, które mają ten sam kształt i objętość).

Edytuj: Tetrahedra nie mogą się przecinać.

Answer 1

Myślę, że podejście oparte na wykresie może działać.

Po pierwsze, listę trójkątnych powierzchni można odzyskać, zauważając, że zestaw krawędzi określa niepokierunkowany wykres G1(V1,E1) dla połączeń między wierzchołkami geometrycznymi. Trójkątna twarz to dowolny cykl długości 3 na tym wykresie.

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 

Następnie czworościany można odzyskać przez formowanie nieukierunkowane wykres G2(V2,E2) określający połączenia pomiędzy powierzchniami (to ścianki są połączone jeśli mają przewagę). Na wykresie czworościan ma długość 4 razy.

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 

Mam nadzieję, że to pomoże.