Tetraeder in einem triangulierten Netz erkennen?

Question

Nehmen wir an, ich habe ein Netz mit Linien, die die Scheitelpunkte so verbinden, dass sie in Tetraeder zerlegt werden können. Gibt es einen Algorithmus, mit dem ich die Präsenz der Tetraeder anhand der Eckpunkte und Linien erkennen kann? (Z. B. gegeben das Gitter mit Verbindungslinien, eine Menge von Tetraedern ausgeben, die die gleiche Form und das gleiche Volumen haben.)

Edit: Tetrahedra dürfen nicht schneiden.

Answer 1

Ich denke, ein Graph-basierter Ansatz kann funktionieren.

Zuerst kann die Liste der dreieckigen Flächen wiederhergestellt werden, indem festgestellt wird, dass die Menge der Kanten einen ungerichteten Graphen G1(V1,E1) für die Verbindung zwischen den geometrischen Eckpunkten definiert. Eine dreieckige Fläche hat in diesem Diagramm einen Zyklus von Länge 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 

Als nächstes kann die -Tetraeder durch Bilden des ungerichteten Graphen G2(V2,E2) Definieren der Konnektivität zwischen den Flächen zurückgewonnen werden (d.h. Flächen verbunden sind, wenn sie eine Kante teilen). Ein Tetraeder ist in diesem Graph ein beliebiger Zyklus von Länge 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 

Hoffe, das hilft.