2013-01-16 32 views
5

Diyelim ki, köşeleri, tetrahedraya bölünmesine izin verecek şekilde bağlayan bir ağa sahip olduğumu düşünelim. Köşeleri ve çizgileri verilen tetrahedranın varlığını tespit etmek için kullanabileceğim bir algoritma var mı? (Yani, bağlantı hatları ile örgü verildiğinde, aynı şekil ve hacme sahip bir dizi tetrahedra çıktı).Üçgen şeklinde bir ağ içinde tetrahedrayı tespit edin?

Düzenleme: Tetrahedra'nın kesişmesine izin verilmez.

+0

Yani, tetrahedrayı oluşturmak için gerekli olan tüm kenarların zaten satır kümesi olarak mevcut olduğunu mu söylüyorsunuz? –

+0

Evet, kenarlar zaten mevcut. –

+0

Hangi formda köşe ve kenarlarınız var? – meyumer

cevap

0

Grafik tabanlı bir yaklaşımın işe yarayabileceğini düşünüyorum. İlk olarak, üçgen kenarlarının listesi, geometrik kenarlar arasındaki bağlantı için kenar kümesi kümesinin, doğrulanmamış bir grafiği G1(V1,E1) tanımladığını belirterek kurtarılabilir. Üçgen bir yüz, bu grafikte herhangi bir uzunluk 3 döngüsüdür.

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 

sonra, tetrahedra yüzleri arasındaki bağlantı (çünkü bunlar bir kenarı paylaşan halinde, yani yüzleri bağlanır) tanımlayan yönsüz grafik G2(V2,E2) oluşturulması ile elde edilebilir. Bir tetrahedra bu grafikte herhangi bir uzunluk 4 döngüsüdür.

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 

Bu yardımcı olur umarım.

İlgili konular