त्रिभुज जाल के भीतर टेट्राहेड्रा का पता लगाएं?

Question

मान लें कि मेरे पास एक जाल है जिसमें शीर्षकों को एक तरह से जोड़ने वाली रेखाएं हैं जो इसे टेट्राहेड्रा में विभाजित करने की अनुमति देती हैं। क्या कोई एल्गोरिदम है जो मैं टेट्राहेड्रा की उपस्थिति का पता लगाने के लिए उपयोग कर सकता हूं ताकि शिखर और रेखाएं दी जा सकें? (यानी, कनेक्टिंग लाइनों के साथ जाल दिया जाता है, एक ही आकार और मात्रा वाले टेट्राहेड्रा का एक सेट आउटपुट करता है।)

संपादित करें: टेट्राहेड्रा को छेड़छाड़ की अनुमति नहीं है।

Answer 1

मुझे लगता है कि एक ग्राफ-आधारित दृष्टिकोण काम कर सकता है।

सबसे पहले, त्रिकोणीय चेहरे की सूची को ध्यान में रखकर पुनर्प्राप्त किया जा सकता है कि किनारों का सेट ज्यामितीय चरम के बीच कनेक्टिविटी के लिए एक अप्रत्यक्ष ग्राफ G1(V1,E1) परिभाषित करता है। इस ग्राफ में त्रिकोणीय चेहरा किसी भी लंबाई 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 

इसके बाद, टेट्राहेड्रा अनिर्दिष्ट ग्राफ G2(V2,E2) चेहरों के बीच संपर्क (अर्थात चेहरे जुड़े हुए हैं अगर वे एक बढ़त का हिस्सा) को परिभाषित करने के गठन से बरामद किया जा सकता। इस ग्राफ में एक टेट्राहेड्रा कोई लंबाई 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 

उम्मीद है कि इससे मदद मिलती है।