यह गैर-तुच्छ लगता है (इसे विभिन्न मंचों पर काफी कुछ पूछा जाता है), लेकिन मुझे इसे एक जटिल जटिल एल्गोरिदम के लिए बिल्डिंग ब्लॉक के रूप में बिल्कुल आवश्यकता है।दो बहुभुजों को कैसे छेड़छाड़ करें?
इनपुट: 2 डी में 2 बहुभुज (ए और बी), किनारों की सूची [(x0, y0, x1, y2), ...]
की सूची के रूप में दिया गया है। अंक double
एस के जोड़े द्वारा दर्शाए जाते हैं। मुझे नहीं पता कि उन्हें घड़ी की दिशा में, विपरीत दिशा में या किसी भी दिशा में दिया गया है या नहीं। मैं जानता हूं कि वे आवश्यक रूप से उत्तल नहीं हैं।
आउटपुट: ए, बी और अंतरंग बहुभुज एबी का प्रतिनिधित्व करने वाले 3 बहुभुज। इनमें से कोई भी खाली (?) बहुभुज हो सकता है, उदा। null
।
अनुकूलन के लिए संकेत: ये बहुभुज कमरे और मंजिल सीमाओं का प्रतिनिधित्व करते हैं। तो कमरे की सीमा आम तौर पर मंजिल सीमा से पूरी तरह से छेड़छाड़ की जाएगी, जब तक कि यह एक ही विमान (argh!) पर किसी अन्य मंजिल से संबंधित न हो।
मुझे आशा है कि किसी ने पहले से ही इसे सी # में किया है और मुझे अपनी रणनीति/कोड का उपयोग करने देगी, जैसा कि मैंने इस समस्या पर अब तक पाया है, बल्कि यह मुश्किल है।
संपादित करें: तो ऐसा लगता है कि मैं ऐसा करने की संभावना पर बेहोश होने के लिए पूरी तरह से चिकन नहीं हूं। मैं, यहां वांछित आउटपुट को फिर से करना चाहते, क्योंकि यह एक विशेष मामला है और सरल गणना कर सकता है जाएगा:
आउटपुट: सबसे पहले बहुभुज शून्य से सभी अन्तर्विभाजक बिट्स, चौराहे बहुभुज (बहुवचन ठीक है)। मैं वास्तव में दूसरे बहुभुज में दिलचस्पी नहीं रखता हूं, केवल पहले के साथ इसका चौराहे।
EDIT2: मैं वर्तमान में GPC (General Polygon Clipper) लाइब्रेरी का उपयोग कर रहा हूं जो इसे वास्तव में आसान बनाता है!
यह आपके विचार से कहीं अधिक जटिल है। आप परिणामी आकार का प्रतिनिधित्व करने की योजना कैसे बनाते हैं? ध्यान रखें कि दो इनपुट (ए) बिल्कुल अंतर नहीं कर सकते हैं, (बी) आंशिक रूप से छेड़छाड़ करते हैं, जिसके परिणामस्वरूप उत्तल या अवतल बंद आकार होता है, (सी) पूरी तरह से छेड़छाड़ करता है, जिसके परिणामस्वरूप दो सीमाओं (यानी डोनट) के साथ एक आकार होता है। आपको आकार के अंदर और बाहर का प्रतिनिधित्व करने का एक तरीका मिलना चाहिए। –
दरअसल, जॉन सही है। आपकी समस्या अच्छी तरह से नहीं कहा गया है; परिणामस्वरूप सेट * बहुभुज * नहीं हो सकता है, और इसलिए फ़ंक्शन का आउटपुट बहुभुज नहीं होना चाहिए। आप उस मामले में क्या करना चाहते हैं जहां परिणामी आकार कनेक्ट नहीं है? उदाहरण के लिए कल्पना करें कि एक सी-आकार वाली पॉली एक आकार के पॉली को छेड़छाड़ कर रही है, जिसके परिणामस्वरूप एक कोलन होता है। –
धन्यवाद, इसके बारे में कठिन सोचना होगा और समाधान के साथ आना होगा। इससे पहले इस तरह से नहीं सोचा था ... –