भरण ऑपरेशन पेंट अनुप्रयोगों में कैसे काम करता है?

Question

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

बातें मैं जल्दी से के बारे में सोच सकते हैं के एक जोड़े हैं:

एक द्विआधारी नक्शा, जहां रंग में पिक्सल को बदला जाएगा में

1. Convert छवि 1 हैं और सभी अन्य रंग 0 हैं।
2. बिंदु के आसपास एक बंद क्षेत्र आप इस तरह बदलना चाहते हैं कि सभी पिक्सल के अंदर 1 कर रहे हैं और सभी पड़ोसी पिक्सल 0.

Sample Image

Answer 1

कई कार्यान्वयन एक पुनरावर्ती को जीत के रूप में किया जाता है और एल्गोरिदम विभाजित करें। यदि आप "बाढ़ भरने वाले एल्गोरिदम" के लिए त्वरित Google करते हैं तो आपको the topic पर उत्कृष्ट विकिपीडिया पृष्ठ सहित बहुत सारे संसाधन मिलेंगे।

Answer 2

आप एक समय कुशल एल्गोरिथ्म है कि स्मृति क्षमता के बारे में बहुत परवाह नहीं करता चाहते हैं, आप इसे से कर सकते हैं:

1) एक बूलियन स्मृति रखने जिनमें से कोशिकाओं आप पहले से ही दौरा किया है: Vis[]

2) अंक आप पहले से ही आने वाले लोगों की सूची में रखते हुए, लेकिन अभी तक के लिए पड़ोसियों के रूप में चिह्नित नहीं किया है: Busy[]

3) शुरू के रूप में खाली उन दोनों

4)के लिए अपने आरंभ बिंदु जोड़ने

5)

while you have a point P in Busy: 
{ 
    for each neighbour N of the point P for which Vis[N] is still false 
    { 
     if appropriate (not crossing the boundary of the fill region) 
     { 
      set Vis[N] to true 
      update the colour of N in the bitmap 
      add N to the end of Busy[] 
     } 
     remove P from Busy[] 
    } 
} 

Answer 3

बाढ़ भरें एल्गोरिथ्म क्या सबसे अधिक इस्तेमाल किया जाता है। निम्नलिखित सीधे मेरे पुराने विश्वविद्यालय पाठ्यपुस्तक से बाहर इसके बारे में एक अनुभवहीन संस्करण है, हार्न बेकर ने "ओपन के साथ कंप्यूटर ग्राफिक्स", 3 एड:

void floodFill4 (int x, int y, int fillColor, int interiorColor) 
{ 
    int color; 

    /* Set current color to fillColor, then perform the following operations */ 
    getPixel(x, y, color); 
    if (color == interiorColor) 
    { 
    setPixel(x,y); // Set color of pixel to fillColor. 
    floodFill4(x + 1, y, fillColor, interiorColor); 
    floodFill4(x - 1, y, fillColor, interiorColor); 
    floodFill4(x, y + 1, fillColor, interiorColor); 
    floodFill4(x, y - 1, fillColor, interiorColor); 
    } 
} 

बड़ी छवियों के लिए, तथापि, ऊपर शायद आप एक ढेर दे देंगे प्रत्येक पिक्सेल के लिए रिकर्सिंग के कारण-ओवरफ्लो त्रुटि। अक्सर, इस एल्गोरिदम को संशोधित किया जाता है ताकि पिक्सेल की पंक्ति भरते समय यह पुनरावृत्ति का उपयोग करता है, फिर ऊपर और नीचे पंक्तियों को फिर से भर देता है। जैसा कि @ कास्परज ने कहा, विकिपीडिया के बारे में एक अच्छा लेख है।

Answer 4

इस प्रकार के एल्गोरिदम पर Computer Graphics: Principles and Practice में विस्तार से चर्चा की गई है। यदि आप डायरेक्टएक्स या ओपनजीएल एपीआई का उपयोग किए बिना 3 डी कोड लिखने, लाइनों को रास्टराइज़ करने, पॉलीगन्स भरने, समझने में रुचि रखते हैं, तो मैं अत्यधिक इस पुस्तक की अनुशंसा करता हूं। बेशक, असली दुनिया के अनुप्रयोगों के लिए, आप शायद मौजूदा पुस्तकालयों का उपयोग करना चाहेंगे, लेकिन यदि आप इस पुस्तकालयों के काम के बारे में उत्सुक हैं, तो यह एक शानदार पढ़ा है।

Answer 5

भी जुड़े घटक लेबलिंग के बारे में पढ़ें। कनेक्टेड पिक्सल खोजने के लिए यह एक प्रभावशाली तरीका है जबकि केवल प्रत्येक पिक्सेल को दो बार जाकर।ढाल शायद -

Wikipedia article.

इस के लिए लाभ यह है कि पिक्सेल मान जरूरी समान या समारोह है कि के रूप में कच्चे मूल्य के अलावा कुछ हो सकता है जुड़ा हुआ पिक्सल का वर्णन होना जरूरी नहीं है।

Answer 6

सामान्य विचार Flood Fill Algorithm के रूप में वर्णित है और इसमें कई संशोधन हैं। एक सामान्य स्कैनलाइन भरना है। संबंधित प्रश्न देखें How Scanline based 2d rendering engines works?