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.
Więc czy mówisz, że wszystkie krawędzie potrzebne do utworzenia czworościanów są już obecne jako zestaw linii? –
Tak, krawędzie są już obecne. –
W jakiej formie masz wierzchołki i krawędzie? – meyumer