अंक S (x, y, z) के एक सेट को देखते हुए। उन बिंदुओं के convex hull कैसे खोजें?एक 3 आयामी अंतरिक्ष में उत्तल हल को कैसे ढूंढें
मैं here से एल्गोरिथ्म को समझने की कोशिश की है, लेकिन बहुत ज्यादा नहीं मिल सकता है।
इसे कहते हैं:
पहले परियोजना xy विमान पर अंक के सभी, और एक बढ़त है कि उच्चतम y- निर्देशांक के साथ बिंदु चुना था और उसके बाद से एक यात्रा करके पतवार पर निश्चित रूप से है किनारे के दूसरे अंतराल को निर्धारित करने के लिए उपहार लपेटना। यह अपूर्ण झोपड़ी का पहला हिस्सा है। फिर हम इसे हलचल बनाते हैं। इस पहले किनारे पर विचार करें; अब हल के पहले त्रिकोणीय चेहरे को बनाने के लिए एक और बिंदु खोजें। हम इस बिंदु को उठाकर ऐसा करते हैं कि अन्य सभी बिंदु इस त्रिभुज के दाईं ओर झूठ बोलते हैं, जब उचित रूप से देखा जाता है (जैसे गिफ्ट-रैपिंग एल्गोरिदम में, जिसमें हमने किनारे को चुना है जैसे कि अन्य सभी बिंदु दाईं ओर हैं वह किनारा)। अब हल में तीन किनारों हैं; जारी रखने के लिए, हम उनमें से एक को मनमाने ढंग से चुनते हैं, और फिर इस किनारे के साथ एक नया त्रिकोण बनाने के लिए एक और बिंदु खोजने के लिए सभी बिंदुओं के माध्यम से स्कैन करते हैं, और इसे तब तक दोहराएं जब तक कोई किनारों न छोड़े जाएं। (जब हम एक नया त्रिकोणीय चेहरा बनाते हैं, तो हम पूल में दो किनारों को जोड़ते हैं, हालांकि, हमें पहले यह जांचना होगा कि क्या उन्हें पहले से ही हल में जोड़ा गया है, इस मामले में हम उन्हें अनदेखा करते हैं।) ओ (एन) चेहरे हैं, और प्रत्येक पुनरावृत्ति ओ (एन) समय लेता है क्योंकि हमें सभी शेष बिंदुओं को स्कैन करना होगा, ओ (एन 2) देना।
क्या कोई इसे अधिक स्पष्ट तरीके से समझा सकता है या एक सरल वैकल्पिक दृष्टिकोण सुझा सकता है।
पर एल्गोरिथ्म एक टिप्पणी छोड़ कृपया अगर कुछ स्पष्ट नहीं है। – anon
ऐसा लगता है कि ओपी 3 डी हल्स के लिए मदद मांग रहा है, लेकिन आपका (अच्छा!) विवरण 2 डी हल्स के लिए है ... –
यदि आप 2 डी समझते हैं, तो 3 डी एक बहुत ही सरल सामान्यीकरण है;) – anon