बहुभुज भरने एल्गोरिथ्म

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

स्कैन लाइन एल्गोरिदम

यह एल्गोरिथ्म बहुभुज किनारों के साथ स्कैनलाइन को इंटरसेक्ट करके काम करता है और बहुभुज को चौराहों के जोड़े के बीच भर देता है। निम्न चरण दर्शाते हैं कि यह एल्गोरिथम कैसे काम करता है।

Step 1 - दिए गए बहुभुज से यमिन और यमैक्स का पता लगाएं।

Step 2- स्कैनलाइन पॉलिन के प्रत्येक किनारे के साथ यमिन से यमैक्स तक जाती है। बहुभुज के प्रत्येक चौराहे का नाम बताएं। ऊपर दिखाए गए आंकड़े के अनुसार, उन्हें p0, p1, P2, p3 के रूप में नामित किया गया है।

Step 3 - X निर्देशांक (p0, p1), (p1, P2), और (P2, p3) के बढ़ते क्रम में प्रतिच्छेदन बिंदु को क्रमबद्ध करें।

Step 4 - निर्देशांक के उन सभी जोड़े को भरें जो बहुभुज के अंदर होते हैं और वैकल्पिक जोड़े को अनदेखा करते हैं।

बाढ़ भरण एल्गोरिथ्म

कभी-कभी हमारे पास एक ऐसी वस्तु होती है, जहाँ हम इस क्षेत्र और इसकी सीमा को अलग-अलग रंगों से भरना चाहते हैं। हम इस तरह की वस्तुओं को एक विशेष आंतरिक रंग के साथ निर्दिष्ट सीमा रंग के रूप में खोज सकते हैं जैसे कि सीमा भरने वाले एल्गोरिथ्म में।

ऑब्जेक्ट की सीमा पर निर्भर होने के बजाय, यह भरण रंग पर निर्भर करता है। दूसरे शब्दों में, यह ऑब्जेक्ट के आंतरिक रंग को भरण रंग से बदल देता है। जब मूल आंतरिक रंग का कोई और अधिक पिक्सेल मौजूद नहीं होता है, तो एल्गोरिथ्म पूरा हो जाता है।

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

सीमा भरण एल्गोरिथ्म

सीमा भरण एल्गोरिथ्म इसके नाम के रूप में काम करता है। यह एल्गोरिथम किसी ऑब्जेक्ट के अंदर एक बिंदु को चुनता है और तब तक भरना शुरू करता है जब तक कि यह ऑब्जेक्ट की सीमा को हिट न कर दे। इस एल्गोरिदम के काम करने के लिए सीमा का रंग और हमारे द्वारा भरा जाने वाला रंग अलग होना चाहिए।

इस एल्गोरिथ्म में, हम मानते हैं कि सीमा का रंग पूरे ऑब्जेक्ट के लिए समान है। सीमा भरण एल्गोरिथ्म को 4-कनेक्टेड पिक्सेल या 8-कनेक्टेड पिक्सेल द्वारा कार्यान्वित किया जा सकता है।

4-कनेक्टेड बहुभुज

इस तकनीक में 4-जुड़े पिक्सेल का उपयोग किया जाता है जैसा कि चित्र में दिखाया गया है। हम ऊपर, नीचे, दाईं ओर और वर्तमान पिक्सेल के बाईं ओर पिक्सेल लगा रहे हैं और यह प्रक्रिया तब तक जारी रहेगी जब तक कि हम अलग-अलग रंग के साथ एक सीमा नहीं पाते।

कलन विधि

Step 1 - सीड पॉइंट (सीडैक्स, सीडाई), फोलर और डॉक के मूल्य को इनिशियलाइज़ करें।

Step 2 - बहुभुज के सीमा मूल्यों को परिभाषित करें।

Step 3 - जांचें कि यदि वर्तमान बीज बिंदु डिफ़ॉल्ट रंग का है, तो चरण 4 और 5 तक दोहराएं जब तक कि सीमा पिक्सेल न पहुंच जाए।

If getpixel(x, y) = dcol then repeat step 4 and 5

Step 4 - बीज बिंदु पर भरण रंग के साथ डिफ़ॉल्ट रंग बदलें।

setPixel(seedx, seedy, fcol)

Step 5 - चार पड़ोस बिंदुओं के साथ फिर से प्रक्रिया का पालन करें।

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)

Step 6 - बाहर निकलें

इस तकनीक के साथ एक समस्या है। नीचे दिए गए मामले पर विचार करें जहां हमने पूरे क्षेत्र को भरने की कोशिश की है। यहां, छवि केवल आंशिक रूप से भरी हुई है। ऐसे मामलों में, 4-कनेक्टेड पिक्सेल तकनीक का उपयोग नहीं किया जा सकता है।

8-कनेक्टेड बहुभुज

इस तकनीक में 8-जुड़े पिक्सेल का उपयोग किया जाता है जैसा कि चित्र में दिखाया गया है। हम वर्तमान पिक्सल के ऊपर, नीचे, दाएं और बाएं तरफ पिक्सेल डाल रहे हैं जैसा कि हम 4-कनेक्टेड तकनीक में कर रहे थे।

इसके अलावा, हम पिक्सेल को विकर्णों में भी डाल रहे हैं ताकि वर्तमान पिक्सेल का पूरा क्षेत्र कवर हो। यह प्रक्रिया तब तक जारी रहेगी जब तक हम अलग-अलग रंग के साथ एक सीमा नहीं पाते।

कलन विधि

Step 1 - सीड पॉइंट (सीडैक्स, सीडाई), फोलर और डॉक के मूल्य को इनिशियलाइज़ करें।

Step 2 - बहुभुज के सीमा मूल्यों को परिभाषित करें।

Step 3 - जांचें कि यदि वर्तमान बीज बिंदु डिफ़ॉल्ट रंग का है, तो सीमा पिक्सेल तक पहुंचने तक चरण 4 और 5 को दोहराएं

If getpixel(x,y) = dcol then repeat step 4 and 5

Step 4 - बीज बिंदु पर भरण रंग के साथ डिफ़ॉल्ट रंग बदलें।

setPixel(seedx, seedy, fcol)

Step 5 - चार पड़ोस बिंदुओं के साथ फिर से प्रक्रिया का पालन करें

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)

Step 6 - बाहर निकलें

4-कनेक्टेड पिक्सेल तकनीक उस क्षेत्र को भरने में विफल रही जैसा कि निम्नलिखित आंकड़े में 8-कनेक्टेड तकनीक के साथ नहीं होगा।

अंदर-बाहर टेस्ट

इस विधि के रूप में भी जाना जाता है counting number method। किसी वस्तु को भरते समय, हमें अक्सर यह पहचानने की आवश्यकता होती है कि वस्तु के अंदर कोई विशेष बिंदु है या उसके बाहर। दो विधियाँ हैं जिनके द्वारा हम यह पहचान सकते हैं कि कोई विशेष बिंदु किसी वस्तु के अंदर है या बाहर।

• विषम-सम नियम
• नॉनजेरो वाइंडिंग नंबर नियम

विषम-सम नियम

इस तकनीक में, हम किसी भी बिंदु (x, y) से अनंत तक की रेखा के साथ किनारे को पार करने की गणना करेंगे। यदि इंटरैक्शन की संख्या विषम है, तो बिंदु (x, y) एक आंतरिक बिंदु है; और यदि इंटरैक्शन की संख्या समान है, तो बिंदु (x, y) एक बाहरी बिंदु है। निम्न उदाहरण में इस अवधारणा को दर्शाया गया है।

उपरोक्त आकृति से, हम देख सकते हैं कि बिंदु (x, y) से, बाईं ओर के अंतः बिंदुओं की संख्या 5 है और दाईं ओर 3 है। दोनों सिरों से, इंटरैक्शन पॉइंट की संख्या विषम है, इसलिए बिंदु को वस्तु के भीतर माना जाता है।

नॉनजरो वाइंडिंग नंबर नियम

इस पद्धति का उपयोग साधारण बहुभुजों के साथ भी किया जाता है ताकि दिए गए बिंदु का परीक्षण किया जा सके कि आंतरिक है या नहीं। इसे बस पिन और रबर बैंड की मदद से समझा जा सकता है। बहुभुज के किनारे में से एक पर पिन को ठीक करें और इसमें रबर बैंड को बांधें और फिर बहुभुज के किनारों के साथ रबर बैंड को खींचें।

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

एक अन्य वैकल्पिक विधि में, बहुभुज के सभी किनारों को दिशा दें। बाईं ओर से एक्स दिशा की ओर परीक्षण करने के लिए बिंदु से एक स्कैन लाइन बनाएं।

• मान 1 को उन सभी किनारों को दें जो ऊपर की दिशा में जा रहे हैं और अन्य -1 दिशा निर्देशों के रूप में।

• किनारे की दिशा के मूल्यों की जाँच करें जिनसे स्कैन लाइन गुजर रही है और उन्हें योग करें।

• यदि इस दिशा मान का कुल योग गैर-शून्य है, तो परीक्षण किया जाने वाला यह बिंदु ए है interior point, अन्यथा यह ए exterior point।

• उपरोक्त आकृति में, हम उन दिशा मानों को जोड़ते हैं जिनसे स्कैन लाइन गुजर रही है फिर कुल 1 - 1 + 1 = 1 है; जो गैर-शून्य है। तो इस बिंदु को एक आंतरिक बिंदु कहा जाता है।