मुझे लगता है कि आकार की पूरी त्रिभुज आपको आवश्यकतानुसार बहुत अधिक गणना है। और त्रिभुज भी आकृति के बाहर झूठ बोलने वाले त्रिभुजों को देता है और यहां तक कि आंशिक रूप से अंदर और आंशिक रूप से बाहर भी उन्हें सही ढंग से पुन: संयोजित करता है, यह भी जटिल है।
प्रस्ताव 1
मैं एक पूरी तरह से अलग दृष्टिकोण के बारे में सोचा।
क्या यह वास्तव में आपके सीएडी कार्यक्रम में इसका उपयोग करने के लिए आंकड़े को 2 आंकड़ों में विभाजित करने की आवश्यकता है? मुझे उम्मीद है कि यह भी ठीक है अगर आप इसे एक लूप में एक आंकड़ा के रूप में वर्णित कर सकते हैं (पॉलीगॉन बनाने वाले बिंदुओं की एक सूची)।
आपको जो चीजों की आवश्यकता है वह उन रेखाओं को ढूंढना है जो आकृति के विभिन्न लूप को जोड़ते हैं और जो पूरी तरह से आकृति के अंदर हैं, ताकि आप लूप को गठबंधन करने के लिए उनका उपयोग कर सकें।
मैं अलग-अलग लूप के सेगमेंट के जोड़े की तुलना करके शुरू करता हूं और एक दूसरे के सबसे नज़दीक सेगमेंट की खोज करता हूं। बाहरी लूप के सभी सेगमेंट की तुलना सभी आंतरिक लूप के सभी सेगमेंट के साथ करना प्रारंभ करें।
व्यावहारिक रूप से, मैं बाहरी लूप के बिंदुओं के साथ बाहरी लूप के बिंदुओं और बाहरी पाश के खंडों के साथ आंतरिक लूप पर बिंदुओं के साथ बाहरी लूप पर बिंदुओं की तुलना करके इसे कार्यान्वित करता हूं। और यदि एक्स या वाई दूरी पहले से मिले छोटी दूरी से बड़ी है तो मैं गणना छोड़कर अनुकूलित करूँगा।
2 सेगमेंट या पॉइंट और सेगमेंट एक दूसरे के सबसे नज़दीकी से आपको एक लाइन प्रदान करेंगे जो लूप को गठबंधन करने के लिए इस्तेमाल किया जा सकता है (या आकृति को विभाजित करने के लिए): उनमें से एक के कोने से रेखा (या बिंदु) लंबवत दूसरे खंड पर। दोष यह है कि आप नए नोड्स जोड़ रहे हैं, लेकिन यह कुशल और हमेशा सही है।
एक बार आपको ऐसी लाइन मिल गई, आंतरिक लूप जो जुड़ा हुआ है और नई लाइन/सेगमेंट को एक संशोधित बाहरी लूप में जोड़ा जा सकता है, जिसमें नया लूप नया लूप बंद करने के लिए दो बार शामिल होता है। आप शेष संशोधित बाहरी लूप के शेष अन्य आंतरिक लूप के साथ तुलना करके प्रक्रिया को दोहरा सकते हैं।
जब सभी आंतरिक लूप का उपयोग किया जाता है तो आपके पास संपूर्ण आकृति का वर्णन करने वाला एक पाश होता है।
आकृति को पूरी तरह से 2 आंकड़ों में विभाजित करने के लिए, आपको एक और अतिरिक्त सेगमेंट की आवश्यकता होगी।
लेकिन मुझे लगता है कि इस बिंदु पर हमारे पास लूप जो आपके आंकड़े का प्रतिनिधित्व करने के लिए अधिकांश सीएडी सॉफ़्टवेयर में उपयोग किया जा सकता है। यह सामान्यीकृत आंकड़ा नहीं है क्योंकि यह स्वयं को छूता है लेकिन सीएडी कार्यक्रम आमतौर पर इसकी परवाह नहीं करते हैं। यह आंकड़े की सतह का प्रतिनिधित्व करने के लिए एक सीएडी कार्यक्रम के लिए पूरी तरह प्रयोग योग्य है।
यदि आप वास्तव में इसे 2 आंकड़ों में पूरी तरह से विभाजित करना चाहते हैं तो आपको आवश्यक अतिरिक्त लाइन 2 सेगमेंट या बेहतर बिंदु और सेगमेंट को एक-दूसरे के निकट खोजकर मिल सकती है यदि आप सेगमेंट और पॉइंट्स के जोड़ों की तुलना को सीमित करते हैं जो लूप के दोनों दिशाओं में पहले से जोड़े गए सभी सेगमेंट द्वारा लूप में अलग हो जाते हैं। सभी जोड़े गए खंड लूप में दो बार होते हैं और इसलिए हमेशा नए लूप के 2 भाग होंगे जो उन सभी से अलग हो जाएंगे। प्रस्ताव 1
के आपके उत्तर पर
टिप्पणी मैं सही नहीं है अभी तक अपना उत्तर टिप्पणी करने के लिए क्योंकि मैं पर्याप्त क्रेडिट नहीं है, इसलिए मैं अपने खुद के जवाब देने के लिए टिप्पणी जोड़ देगा।
मैं आपका उदाहरण देख रहा हूं, जिसे मैंने पहले गलत व्याख्या की थी, इसलिए मैंने इस टिप्पणी को अनुकूलित किया।
आपके पास 3 छेद हैं, इसलिए एल्गोरिदम का पहला भाग आपके द्वारा दिखाए जा रहे 3 सेगमेंट जोड़ देगा।
और, हाँ, आपको स्पष्ट रूप से एल्गोरिदम के दूसरे भाग के लिए समस्या का मामला है। आपको चौथी रेखा की आवश्यकता है, लेकिन इस मामले में कोई 2 भाग नहीं हैं, जो दोनों दिशाओं में सभी 3 अतिरिक्त सेगमेंट से अलग होते हैं या मैं उन्हें तुरंत नहीं देखता हूं।
मुझे लगता है कि हमेशा नए लूप के 2 भाग होंगे जो सभी नए खंडों से अलग हो जाएंगे। जब 3 छेद या अधिक होते हैं तो यह धारणा गलत होती है।
लेकिन मैं इसके बारे में और सोचूंगा।
प्रस्ताव 2
मैं अब एक और संभावित एल्गोरिदम के बारे में सोच रहा हूँ।
आकृति में प्रत्येक छेद की सतह की गणना। प्रत्येक छेद के एक कोने उठाओ।
सबसे छोटे 2 छेद के चुने हुए कोनों के माध्यम से एक रेखा बनाएं।
यह 2 छेद हो सकता है, लेकिन सबसे छोटे लोगों को कम लाइनों के साथ अधिक छेद काटने का मौका बढ़ जाता है।
यदि केवल एक छेद छोड़ा गया है, तो बस एक बिंदु के माध्यम से एक रेखा खींचें। अभिविन्यास कोई फर्क नहीं पड़ता। मैं चुने हुए बिंदु और छेद को परिभाषित करने वाले निकटतम अन्य बिंदु के माध्यम से रेखा खींचना चुनूंगा।
आकृति के खंडों के साथ रेखा को कम करने के लिए रेखा के सभी चौराहे का पता लगाएं, जो कि आकृति के अंदर पूरी तरह से हैं और आकृति के विभिन्न लूप को जोड़ते हैं। उसी लूप पर अंत अंत शुरू करने वाले किसी सेगमेंट को छोड़ दें।
यदि एक छेद केवल एक बिंदु में पाए गए खंडों से छूता है। बाहर से छूने वाले छेद वाले आकृति के साथ समाप्त होने से बचने के लिए उस बिंदु के निकटतम छेद के बिंदु पर एक सेगमेंट को ले जाएं। संशोधित सेगमेंट के साथ नए चौराहे की जांच करें और यदि कोई पाया जाए तो इसे फिर से विभाजित करें।
सभी छेड़छाड़ों को ढूंढने के लिए आकृति के सभी खंडों में मिली रेखा की तुलना करने की आवश्यकता होती है जो कि बहुत अधिक गणना है, लेकिन आप यह जांच करके गणना छोड़ सकते हैं कि रेखा चौराहे की गणना करने से पहले एक सेगमेंट के चारों ओर बाउंडिंग बॉक्स को पार करती है। मैं बाहरी लूप के साथ चौराहे की गणना करके लाइन के शेष भाग के लिए जितनी जल्दी हो सके बाध्यकारी बॉक्स की गणना करके शुरू करूंगा क्योंकि इससे उन अनुभागों की जांच करने में भी मदद मिल सकती है जिन्हें आपको चौराहे के लिए तुलना करने की आवश्यकता नहीं है।
आप कनेक्ट किए गए सेगमेंट के निकटतम अंत बिंदुओं को जोड़ने वाले सेगमेंट द्वारा प्रत्येक मिले सेगमेंट को प्रतिस्थापित करके ऑप्टिमाइज़ भी कर सकते हैं (यदि पहले से ही 2 सेगमेंट के कनेक्शन बिंदु में नहीं हैं)। ऐसा करने से नए आंकड़ों के लिए अतिरिक्त अंक पैदा करने से बचा जाता है और एक चरण में अधिक छेद से छुटकारा पाने का मौका बढ़ जाता है। लेकिन फिर आपको नए चौराहे के लिए फिर से जांचना होगा और इस ऑप्टिमाइज़ेशन को तब तक दोहराना होगा जबतक कि आपको कोई और चौराहे न मिले।
और एक और संभावित अनुकूलन: छेद के बिंदुओं की जांच करें जो अभी तक नहीं पाए गए हैं जो पाए गए सेगमेंट के नजदीक हैं और उस सेगमेंट को उसी चरण में पकड़ने के लिए 2 सेगमेंट में मिले सेगमेंट को विभाजित करें। पिछले अनुकूलन की तरह, इसे फिर से नए चौराहे की जांच करने की आवश्यकता है।
आकृति को 2 आंकड़ों में विभाजित करने के लिए सेगमेंट का उपयोग करें और प्रत्येक नए आकृति के लिए चरण 2 से दोहराएं जिसमें अभी भी छेद है।
दोष यह है कि आप अधिक से अधिक 2 आंकड़े (अधिकतम (एन एन छेद की संख्या होने के साथ +1)/2 आंकड़े) के साथ खत्म हो सकता है, लेकिन अगर आप कई कई आंकड़े में जिसके परिणामस्वरूप छेद है यह उनमें से कुछ को पुनः संयोजित करना संभव हो सकता है।
कारण है कि मैं विवश डेलॉनाय ट्राईऐन्ग्युलेशंस का उपयोग करें कि:
लेकिन डेल्यूने त्रिकोण और यहां तक कि अधिक बाध्यकारी भाग फ्लोटिंग पॉइंट परिशुद्धता और एल्गोरिदमिक अस्थिरता के कारण कठिन इनपुट के लिए विफल रहता है। मेरा इनपुट कभी-कभी ऊंचाई 1e-8 और आधार लंबाई के साथ त्रिकोण उत्पन्न करता है।
यह प्रश्न स्क्रीनशॉट या किसी प्रकार के चित्रण से लाभान्वित होगा। – Wossname
संपादित करें: कुछ चित्रण अनुरोध पर। – PanicSheep
आपको https://gis.stackexchange.com/ पर पोस्ट करने के लिए और अधिक भाग्य हो सकता है भले ही यह सीएडी है –