बहुभुज एल्गोरिदम भरते हैं

आज मैंने फिल एल्गोरिथम पर एक दिलचस्प लेख पढ़ा और इसे थोड़ा पूरक करने का फैसला किया। यदि मूल लेख में मनमानी क्षेत्रों को भरने के बारे में बात की गई है, तो हम बहुभुजों को भरने के एक विशेष, लेकिन अधिक सामान्य मामले के बारे में बात करेंगे।
इस विषय में, हम एल्गोरिदम के तीन समूहों पर विचार करते हैं:

• बीज भरण एल्गोरिथ्म
• बढ़त बिंदुओं की सूची के साथ एल्गोरिदम
• XOR एल्गोरिदम

बीज भरण एल्गोरिथ्म

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

1. स्टैक पर बीज पिक्सेल रखें ;
2. स्टैक से एक पिक्सेल निकालें ;
3. पिक्सेल ( आंतरिक क्षेत्र का रंग ) के लिए वांछित मान असाइन करें ;
4. प्रत्येक पड़ोसी पिक्सेल को स्टैक में जोड़ा जाता है, अगर यह है
4.1। यह सीमा नहीं है ;
4.2। पहले से संसाधित नहीं किया गया ( यानी इसका रंग सीमा के रंग या आंतरिक क्षेत्र के रंग से भिन्न होता है ) ;
5. यदि स्टैक खाली नहीं है, तो चरण 2.6 पर जाएं

बेशक, आप एक चार और आठ-जुड़े पड़ोस का उपयोग कर सकते हैं।
इस एल्गोरिथ्म में फायदे की तुलना में अधिक कमियां हैं: यह धीमा है और स्टैक के लिए बहुत अधिक मेमोरी का उपभोग करता है, इसलिए यह एल्गोरिदम के अगले समूह पर जाने के लिए बहुत अधिक सही होगा।

बढ़त बिंदुओं की सूची के साथ एल्गोरिदम

यह एल्गोरिथ्म केवल उन मामलों के लिए उपयुक्त है जहां छायांकित क्षेत्र को बहुभुज के रूप में निर्दिष्ट किया जा सकता है। हम मानते हैं कि हम लंबवत P1, P2, ..., PN, P1 के साथ एक बहुभुज के साथ काम कर रहे हैं और हम इसे सभी आंतरिक बिंदुओं के साथ स्क्रीन पर प्रदर्शित करना चाहते हैं। सुविधा के लिए, हम मानते हैं कि बहुभुज के प्रत्येक किनारे को इसके छोरों X1, y1 और x2, y2 (y2≥y1 के साथ) के निर्देशांक द्वारा दिया गया है। हम यह भी स्वीकार करते हैं कि बाएं से दाएं की ओर बढ़ने पर x समन्वय बढ़ता है, और y ऊपर से नीचे की ओर बढ़ने पर समन्वय करता है।
बहुभुज रेखांकन एल्गोरिदम के विशाल बहुमत निम्नलिखित धारणा पर आधारित हैं: कोई भी धर्मनिरपेक्ष रेखा बहुभुज सीमा को एक समान संख्या में काटती है। यह कथन केवल दो मामलों में सत्य है:

• जब एकांत रेखा में एक धार होती है;
• जब किसी धर्मनिरपेक्ष रेखा में एक शीर्ष रेखा होती है, और निकटवर्ती किनारे एकांत रेखा के एक तरफ स्थित होते हैं।

इन दो मामलों का पता लगाना काफी आसान है, इसलिए, जब बहुभुजों को व्यवस्थित करने के लिए एल्गोरिदम पर विचार करते हैं, तो हम मानते हैं कि उपरोक्त धारणा हमेशा सच है।

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

दूसरे चरण में, y के प्रत्येक मान के लिए, सूचियों को आरोही क्रम में क्रमबद्ध किया जाता है। उसके बाद, सूचियाँ इस तरह दिखाई देंगी:

तीसरे चरण में, प्रत्येक y के लिए, सभी प्राप्त खंड भरे हुए हैं।
इस एल्गोरिथ्म का लाभ यह है कि प्रत्येक पिक्सेल को एक बार सख्ती से संसाधित किया जाता है। इस प्रकार यह तर्क दिया जा सकता है कि यह एल्गोरिथ्म उन उपकरणों के लिए उपयुक्त है, जहां वीडियो मेमोरी तक पहुंचने में अपेक्षाकृत लंबा समय लगता है।
स्मृति के उपभोग के लिए अनुकूलित इस एल्गोरिथ्म का एक संशोधन है। इसमें, प्रत्येक चरण पर, केवल उन किनारों को संसाधित किया जाता है जो वर्तमान स्कैन लाइन के साथ प्रतिच्छेद करते हैं।

XOR एल्गोरिदम

XOR लाइन-बाय-लाइन प्रोसेसिंग

यह बहुभुज रेखांकन विधि एक तार्किक XOR ऑपरेशन के गुणों पर आधारित है।

यह एल्गोरिथ्म, एल्गोरिथ्म की तरह, बढ़त बिंदुओं की सूची के साथ, सीमाओं को रेखापुंज करने के साथ शुरू होता है। सीमाएं बनने के बाद, छायांकन को दो छायांकित बिंदुओं के बीच प्रत्येक पंक्ति में अंतराल को भरने के लिए कम किया जाता है।
छवि को एक बाइनरी सरणी के रूप में कल्पना करें। हम सहमत हैं कि जब मैं पिक्सेल छायांकित करता हूं, तो मैं [x; y] = 1, और जब पिक्सेल छायांकित नहीं होता है, तो मैं [x; y] = 0। यह देखना आसान है कि ऑपरेशन I [x + 1, y] = I [x; y] XOR I x + 1; y] को एक पंक्ति में सभी पिक्सेल पर लागू करने से लगभग सही परिणाम प्राप्त होगा। इस ऑपरेशन के परिणामस्वरूप, सभी अंतराल भरे जाएंगे, लेकिन प्रत्येक अंतराल में अंतिम पिक्सेल नहीं भरा जाएगा। ज्यादातर मामलों में, यह त्रुटि नगण्य और अगोचर है, लेकिन यदि आप एक सटीक परिणाम प्राप्त करना चाहते हैं, तो आप एल्गोरिथ्म को पूरा करने के बाद स्क्रीन पर सीमाओं को फिर से प्रदर्शित कर सकते हैं, या इस एल्गोरिथ्म के एक छोटे से संशोधन का उपयोग कर सकते हैं।

y के लिए : = 1 से YMax करते हैं
शुरू करना
fl : = false ;
एक्स के लिए : = 1 से एक्समैक्स करते हैं
शुरू करना
अगर मैं [ x , y ] = 1 तो
fl : = fl नहीं ;
अगर तब
मैं [ एक्स , वाई ] : = 1 ;
अंत ;
अंत ;

इस एल्गोरिथ्म का लाभ इसकी चरम सादगी और उच्च गति है। नुकसान यह है कि एल्गोरिथ्म काम नहीं कर सकता है अगर वहाँ बाहरी चित्र हैं।

चेहरे के लिए XOR एल्गोरिथम

चेहरों के लिए XOR विधि निम्नलिखित सरल एल्गोरिथ्म द्वारा वर्णित है: बहुभुज में प्रत्येक किनारे के लिए, इस किनारे के दाईं ओर स्थित सभी पिक्सेल के रंग उल्टे हैं। इसके अलावा, किनारों को ट्रेस करने का क्रम मायने नहीं रखता है। तालिका इस एल्गोरिथ्म (घड़ी की गति) के चरणों को दिखाती है:

इस एल्गोरिथ्म का नुकसान इसकी उच्च समय खपत है, क्योंकि कुछ पिक्सेल एक से अधिक बार संसाधित होते हैं। इसके अलावा, स्क्रीन क्षेत्र के दाईं ओर की छवि से दूरी जितनी अधिक होगी, उतने ही अनावश्यक ऑपरेशन किए जाएंगे।

विभाजन किए गए चेहरे के लिए XOR एल्गोरिथम

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