मेरे पास नीचे की तरह एक जाली है जिसमें जुड़े त्रिकोणों के समूह हैं। मुझे त्रिभुज समूहों का पता लगाना है। क्या इस कार्य के लिए कोई सुविधाजनक उपकरण या एल्गोरिथम है? मैं शोध कर रहा हूँ और मुझे डर है कि कहीं ऐसा कुछ हो सकता है जिससे मैं अनजान हूँ!

Teapot overhang mesh

1
user3405291 31 जिंदा 2019, 10:47

2 जवाब

सबसे बढ़िया उत्तर

एक सरल उपाय यह होगा कि एक मल्टीमैप रखा जाए जिसकी कुंजियाँ 3D बिंदु हों जो सभी त्रिभुजों के शीर्ष हों। यदि एक त्रिभुज एक शीर्ष को दूसरे के साथ साझा करता है, तो हम मान सकते हैं कि वे जुड़े हुए हैं।

अब यह जानकारी रखने के लिए कि कौन से त्रिभुज किस समूह से संबंधित हैं, आप संघ-खोज डेटा संरचना का उपयोग कर सकते हैं ( https://en.wikipedia.org/wiki/Disjoint-set_data_structure) जिसमें लगभग रैखिक जटिलता है।

2
ciamej 31 जिंदा 2019, 11:05

आपके "जुड़े त्रिकोणों के समूह" को खोजने के लिए एक ग्राफ एल्गोरिदम का उपयोग किया जा सकता है।

ग्राफ़ शब्दावली में, आपके त्रिभुज जाल ग्राफ़ होते हैं। आपको ज्यामिति की परवाह नहीं है, आप केवल कनेक्टिविटी की परवाह करते हैं। उदाहरण के लिए आप प्रत्येक 3D शीर्ष को ग्राफ़ के नोड के रूप में और प्रत्येक त्रिभुज किनारे को दो नोड्स को जोड़ने वाले ग्राफ़ के किनारे के रूप में देख सकते हैं।

आपके "जुड़े त्रिकोणों के समूह" ग्राफ शब्दावली में जुड़े हुए घटक होंगे।

ग्राफ में सभी जुड़े घटकों को खोजने के लिए एक कुशल एल्गोरिदम इस उत्तर में देखा जा सकता है:

https://stackoverflow.com/a/21078752/9147444

जो यूनियन-फाइंड डेटास्ट्रक्चर का उपयोग करता है (जिसे डिसजॉइंट-सेट भी कहा जाता है)

1
Mauricio Cele Lopez Belon 1 फरवरी 2019, 19:41