Rileva tetraedri all'interno di una maglia triangolare?

Question

Diciamo che ho una maglia che ha linee che collegano i vertici in un modo che permetterebbe di essere suddiviso in tetraedri. C'è un algoritmo che posso usare per rilevare la presenza del tetraedro dato i vertici e le linee? (I.e, data la maglia con linee di collegamento, emettere un insieme di tetraedri che hanno la stessa forma e volume.)

Modifica: I tetraedri non possono intersecare.

Answer 1

Penso che un approccio grafico-based può funzionare.

Innanzitutto, è possibile recuperare l'elenco di facce triangolari notando che l'insieme di spigoli definisce un grafico non indirizzato G1(V1,E1) per la connettività tra i vertici geometrici. Una faccia triangolare è un qualsiasi ciclo di lunghezza 3 in questo grafico.

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 

Avanti, tetraedri può essere recuperato formando il grafo non orientato G2(V2,E2) definire la connettività tra facce (cioè le facce sono connessi se condividono un bordo). Un tetraedro è un qualsiasi ciclo di lunghezza 4 in questo grafico.

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 

Spero che questo aiuti.