सरल बहुभुज

Question

मैं नीचे के रूप में एक बहुभुज सी राशि प्राप्त करें:

C = 10  0 
    2  0 
    2  2 
    0  2 
    2  0 
    0  0 
    0 10 
    10 10 

जहां प्रथम स्तंभ का प्रतिनिधित्व करता है एक्स के समन्वय और दूसरे स्तंभ y के लिए इसी है की आप के रूप में बहुभुज सी का समन्वय उपरोक्त तस्वीर में देख सकते हैं, यह एक साधारण बहुभुज नहीं है (इस बहुभुज में एक छेद होता है जो सफेद रंग द्वारा निर्दिष्ट होता है), इसलिए मैं सी से सभी सरल उप-बहुभुज प्राप्त करना चाहता हूं जिसमें छेद नहीं होता है। इस मामले उत्पादन में निम्नलिखित के रूप में किया जाना चाहिए:

C1 = 0  2 
      2  0 
      0  0 

    C2 = 2  0 
      2  2 
      0  2 
      0 10 
     10 10 
     10  0 

कहाँ C1 और C2 छोटे लाल त्रिकोण और बड़ा लाल बहुभुज को क्रमशः इसी रहे हैं।

समस्या यह है कि मैं इस उप-बहुभुज को कैसे उत्पन्न कर सकता हूं?

किसी भी विचार की सराहना की जाएगी।

Answer 1

सबसे पहले हम मान सकते हैं कि सभी चौराहे बिंदु मौजूद हैं? बहुभुजों के साथ आना आसान है जो खुद को दिलचस्प तरीके से छेड़छाड़ करते हैं। हालांकि http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm जैसे कुछ का उपयोग करके आप सभी चौराहे में ढूंढ और जोड़ सकते हैं।

अगला मैं सरलीकृत धारणा कर दूंगा कि हम कभी भी लाइन सेगमेंट को पीछे नहीं लेते हैं। (आप विभिन्न तरीकों से उस रोगजनक मामले से निपट सकते हैं।)

उस विवरण के साथ, हमें उन सभी न्यूनतम बहुभुजों को ढूंढने की आवश्यकता है जिन्हें उन बिंदुओं द्वारा परिभाषित किया जा सकता है, चाहे उन्हें अंततः गिना जाता है या नहीं अंदर या बहार। (सुविधा के लिए हम अनंत पर एक "बिंदु" जोड़ देंगे और बाहरी को बहुभुज के रूप में गिनेंगे।) ऐसा करने के लिए हम पहले प्रत्येक बिंदु लेते हैं, और उन बिंदुओं को सूचीबद्ध करते हैं जो इसे सीधे घड़ी के क्रम में जोड़ते हैं। (एक्स-अक्ष के समानांतर यात्रा 0 डिग्री है, वाई धुरी 90 डिग्री है, नकारात्मक एक्स-अक्ष 180 डिग्री है, और फिर जब आप आगे जाते हैं तो हम चारों ओर लपेटते हैं।) तो आपके उदाहरण के लिए हमें कुछ मिल जाएगा इस तरह:

(0, 0): (2, 0), (0, 2) 
(2, 0): (10, 0), (2, 2), (0, 2), (0, 0) 
(10, 0): (10,10), (2, 0) 
(0, 2): (0, 0), (2, 0), (2, 2), (0,10) 
(2, 2): (2, 0), (0, 2) 
(0, 10): (0, 2), (10,10) 
(10, 10): (10, 0), (0,10) 

अब हर सरल बहुभुज उन बिंदुओं की दोनों के बीच प्रत्येक बिंदु मारा जाएगा, और इसके विपरीत हम (लगभग चादर सहित) और आसानी से जुड़े बहुभुज उत्पन्न उन अंतराल में से एक ले जा सकते हैं, पर प्रत्येक कोने सबसे छोटा संभव घुमावदार मोड़ बनाते हैं (यानी उस बिंदु से हम संभवतः लपेटने के बाद एक के पास आए थे)। प्रत्येक रेखा खंड के लिए बहुभुज दायीं तरफ होगा। हम जानते हैं कि हमारे पास उनमें से सभी हैं जब हमारे पास प्रत्येक बिंदु और अंतर होता है। इसलिए उपरोक्त मामले में हम (0, 0) की तरह एक बिंदु के साथ शुरू करते हैं और निम्नलिखित बिंदु (2, 0), तो हम (2, 0) को देखो और लगता है कि (0, 0)(10, 0) द्वारा पीछा किया जाता था, (10, 0) के पास जाकर लगता है कि (2, 0)(10,10) द्वारा पीछा किया जाता है और इस तरह से आगे बढ़ना बाहर का पता लगाने के:

(0, 0), (2, 0), (10, 0), (10,10), (0,10), (0, 2), (0, 0) 

(।, नोट कारण उन्मुखीकरण को यह बाहर क्षेत्र का पता लगाया)

अब हम (0, 0) के साथ शुरू और वैकल्पिक प्रारंभिक बिंदु (0, 2) और प्राप्त करने के लिए एक ही ऑपरेशन करें:

(0, 0), (0, 2), (2, 0), (0, 0) 

(यह छोटा आंतरिक त्रिभुज है।)

(2, 0) के लिए हमने अभी तक (2, 2) पर यात्रा नहीं की है। तो चलो करते हैं।

(2, 0), (2, 2), (0, 2), (0,10), (10,10), (10,0), (2, 0) 

(इस बड़े अनियमित बहुभुज है।)

(2, 0) हम अभी तक (0, 2) के लिए कूच नहीं किया है के लिए तो यह है कि करते हैं: (। इस छोटे सफेद त्रिकोण है)

(2, 0), (0, 2), (2, 2), (2, 0) 

और फिर संभवतः सभी संभव निर्देशित लाइन सेगमेंट का एक गणना हम यात्रा करना चाहते हैं, यह पता चल जाएगा कि हमने उन्हें सभी को कवर किया है। तो ये हमारे बहुभुज हैं। अब हम यह पता लगाने के लिए बाएं हैं कि अंदर क्या है और बाहर क्या है। इसके लिए एक साधारण चाल है। वाई के सबसे कम संभव मूल्य के साथ एक बिंदु खोजें (यदि कोई टाई है, तो कोई भी करेगा)। उदाहरण के लिए मान लीजिए कि हमने (2, 0) चुना है। कनेक्टिंग पॉइंट्स, जो घड़ी की दिशा में व्यवस्थित थे, (10, 0), (2, 2), (0, 2), (0, 0) थे। वे क्रमशः बाहर, अंदर, बाहर, अंदर ... और इसके अलावा एक दिए गए बहुभुज के एक किनारे को बाहर या अंदर के रूप में चिह्नित किया जाता है, इसके सभी निर्देशित किनार समान होते हैं। इस प्रकार हम आसानी से प्राप्त करते हैं:

outside: 
    - (10, 0), (2, 2), (0, 2), (0, 0) 
    - (2, 0), (0, 2), (2, 2), (2, 0) 

inside: 
    - (2, 0), (2, 2), (0, 2), (0,10), (10,10), (10, 0), (2, 0) 
    - (0, 0), (0, 2), (2, 0), (0, 0) 

और आपका उत्तर केवल अंदरूनी बहुभुज होगा।

(छोटे अनुकूलन, हमें बाहरी बहुभुजों को बिल्कुल आकर्षित करने की आवश्यकता नहीं है। हम पहले लाइन सेगमेंट ले सकते हैं जिसका अभिविन्यास हम खोजते हैं, अंदरूनी एक का पता लगाते हैं, फिर अपने कोनों में से एक पर जाते हैं, अभिविन्यास की पहचान करते हैं उस कोने को छूने वाले रेखा खंडों में से, और बहुभुज के अंदर अन्य ड्राइंग शुरू करना। अगर हम सही तरीके से ट्रैक रखते हैं, तो हम अंततः उन्हें सभी प्राप्त करेंगे।)