2 डी असंगठित पॉइंटक्लाउड

Question

का समोच्च खोजें मेरे पास 2 डी अंक, असंगठित का एक सेट है, और मैं इस सेट के "समोच्च" को ढूंढना चाहता हूं (उत्तल हल नहीं)। मैं अल्फा आकार का उपयोग नहीं कर सकता क्योंकि मेरे पास गति का उद्देश्य है (औसत कंप्यूटर पर 10ms से कम)। मेरा पहला दृष्टिकोण ग्रिड की गणना करना और रूपरेखा वर्गों को ढूंढना था (वर्ग जो पड़ोसी के रूप में खाली वर्ग है)। तो मुझे लगता है कि मैंने कुशलता से मेरी संख्याओं की संख्या घटा दी है (22000 से 3000 तक)। लेकिन मुझे अभी भी इस नए सेट को परिष्कृत करने की जरूरत है।

मेरा प्रश्न है: मैं कैसे पता करूँ असली मेरी हरी अंक के बीच अंक की रूपरेखा?

Answer 1

प्रति सप्ताह एक सप्ताहांत के बाद, मुझे एक सुविधाजनक समाधान मिल सकता है।

तो हमें एक ग्रिड की आवश्यकता है, हमें इसे अपने अंक से भरने की जरूरत है, यहां कोई कठिनाई नहीं है।

हमें यह तय करना होगा कि किन वर्गों को "कंटूर" के रूप में माना जाता है। हमारा मानदंड है: कम से कम एक खाली पड़ोसी और कम से कम 3 गैर खाली पड़ोसियों।

हमारे पास कनेक्टिविटी जानकारी की कमी है। तो हम एक "कंटूर" वर्ग चुनते हैं जो 2 "कंटूर" पड़ोसियों या उससे कम के रूप में होता है। फिर हम पड़ोसी में से एक चुनते हैं। उस से, हम विस्तार शुरू कर सकते हैं। हम पिछले "कंटूर" वर्ग को जानने के लिए, अगले "कंटूर" वर्ग को खोजने के लिए वर्तमान वर्ग के चारों ओर सर्कल करते हैं। हमारे समोच्च मानदंड हमें मृत अंत से रोकते हैं।

अब हमारे पास कनेक्टेड वर्गों के वैक्टर हैं, और आम तौर पर यदि हमारे आकार में छेद नहीं है, तो कनेक्टेड वर्गों का केवल एक वेक्टर है!

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

लाल अंक हरी एक की समोच्च हैं। इस्तेमाल की जाने वाली तकनीक विमान बेरिएंटर एक है।

28000 अंक के सेट के लिए, इस तकनीक में 8 एमएस लगते हैं। सीजीएएल के अल्फा आकार 28000 अंकों के लिए औसत 125 एमएस ले जाएगा।

पुनश्च: मैं मैं अपने आप को स्पष्ट कर दिया है उम्मीद है, अंग्रेजी मेरी मातृभाषा नहीं है: रों

Answer 2

आपको वास्तव में अल्फा आकार का उपयोग करना चाहिए। शायद अल्फा अल्फा एल्गोरिदम के इनपुट के रूप में केवल हरे रंग के बिंदुओं का उपयोग करें।