मैं उन सभी आयतों को कैसे ढूंढ सकता हूं जो बिटमैप में क्षेत्रों को बाध्य करते हैं?

Question

मुझे कोई समस्या है: मुझे अपने टाइल इंजन के लिए एल्गोरिदम चाहिए।

मेरे पास 2 डी-सरणी है जो मेरे अन-चलने योग्य टाइल्स स्टोर करती है।

अब मैं एक हल्का इंजन लागू करना चाहता हूं, लेकिन इस इंजन को छाया-हल्स की आवश्यकता है।

तो मुझे एक एल्गोरिदम चाहिए जो इन छाया-हलों को बनाएगा।

मैं आयतों कि सरणी के अन-चलने योग्य भागों (कोशिकाओं है कि 1 रों)
, उदाहरण के लिए बाध्य का एक सेट की जरूरत है:

काले टाइल 1 रों हैं; मुझे लाल आयतों के सेट को खोजने की ज़रूरत है जो उन्हें पूरी तरह से घेर लेते हैं। इस प्रकार

Answer 1

आगे सोचा के बाद, मैं एक तेजी से समाधान के साथ आ गया है:

1. साथ StartX, StartY, और EndY गुण अपरिवर्तनीय Range struct बनाएँ।

2. वर्तमान Range एस की एक स्पैस सरणी बनाए रखें, छवि की ऊंचाई के बराबर लंबाई के साथ, और एक एकल शून्य वर्तमान रेंज चर।

   1. : यह सरणी स्तंभ में प्रत्येक कक्ष के लिए
      1. साफ़ currentRange

      2. , रेंज शामिल यदि कोई हो, कि प्रत्येक Y पर शुरू होता है समन्वय

      3. प्रत्येक कॉलम के लिए होगा,

         यदि कोई मौजूदा श्रेणी नहीं है, या यदि वहां है लेकिन यह इस सेल (यदि currentRange.EndY <= y) से पहले समाप्त हो गया है, तो श्रेणी रेंज में y 'वें तत्व पर वर्तमान रेंज सेट करें।
         इस प्रकार, currentRange वर्तमान सेल में मौजूद सीमा को संदर्भित करेगा, या वर्तमान सेल, या null यदि वर्तमान सेल किसी सीमा में नहीं है।

      4. वर्तमान सेल 1 है:

         1. हम एक सीमा में कर रहे हैं, कुछ भी नहीं – रेंज अगले कॉलम में जारी कर दिया जाए।

         2. हम एक श्रेणी में नहीं हैं, तो स्तंभ नीचे पाश जब तक हम एक 0 या एक स्तंभ के अंत में, तो एक नई रेंज 1 से खींच बनाने के हम सिर्फ पाश के अंत तक पाया मारा।
            फिर, आगे बढ़ें यदि (वर्तमान सेल अब 0 या कॉलम के अंत में है, और हम एक सीमा में नहीं हैं)
            यदि आप मौजूदा सीमा को दबाते हैं तो आप नई सीमा बनाने के लिए आगे बढ़ते हैं , आप या तो नई रेंज को रोक सकते हैं और मौजूदा रेंज को नीचे रख सकते हैं (फजी किनारों के लिए सबसे अच्छा), या मौजूदा रेंज को बंद करें (नीचे देखें) और मौजूदा रेंज से नई सीमा को नीचे ले जाने दें।

      5. वर्तमान सेल 0 यह है:
         1. हम एक सीमा में कर रहे हैं, सीमा बंद:
            1. वापसी एक नए आयत रेंज की आरंभ एक्स और वाई वर्तमान Y तक खींच और सीमा का अंत एक्स
            2. सक्रिय श्रेणियों की सरणी से सीमा साफ़ करें।

इस एल्गोरिथ्म गणना में O(x * y) और अंतरिक्ष में O(y) है। मेरा मानना ​​है कि यह समस्या का सबसे तेज़ समाधान है।

आप इस एल्गोरिदम को घुमा सकते हैं और कॉलम के बजाए पंक्तियों को स्कैन कर सकते हैं (ताकि सीमाएं दाएं की बजाय नीचे की ओर फैली हों), जो भंडारण में O(x) होगी।

class BoxFinder { 
    class Range { 
     public Range(int startX, int startY, int endY) { 
      StartX = startX; 
      StartY = startY; 
      EndY = endY; 
     } 

     public int StartX { get; private set; } 
     public int StartY { get; private set; } 
     public int EndY { get; private set; } 
    } 
    public BoxFinder(int[,] data) { 
     Data = data; 
     Width = data.GetLength(0); 
     Height = data.GetLength(1); 
     ranges = new Range[Height]; 
    } 

    public int[,] Data { get; private set; } 
    public int Width { get; private set; } 
    public int Height { get; private set; } 

    private Range[] ranges; 
    public IEnumerable<Rectangle> GetBoxes() { 
     for (int x = 0; x < Width; x++) { 
      Range currentRange = null; 
      for (int y = 0; y < Height; y++) { 
       Func<Range, Rectangle> CloseRange = r => { 
        currentRange = null; 
        ranges[r.StartY] = null; 
        return new Rectangle(
         r.StartY, 
         r.StartX, 
         x - r.StartX, 
         r.EndY - r.StartY 
        ); 
       }; 

       if (currentRange == null || currentRange.EndY <= y) 
        currentRange = ranges[y]; 

       if (Data[x, y] == 1) { 
        if (currentRange == null) { 
         int startY = y; 
         for (; y < Height && Data[x, y] == 1; y++) { 
          if (ranges[y] != null) 
           yield return CloseRange(ranges[y]); 
          //If there are fuzzy edges, break; instead 
         } 
         ranges[startY] = new Range(x, startY, y); 
         if (y == Height) 
          continue; 
         //Otherwise, continue to the next if in case a previous range just ended 
        } 
       } 
       //No else; we can get here after creating a range 
       if(Data[x, y] == 0) { 
        if (currentRange != null) 
         yield return CloseRange(currentRange); 
       } 
      } 
     } 
    } 
} 

Answer 2

कोशिश कुछ:

1. हर वांछित बिंदु युक्त एक सूची बनाएं। (आपके मामले में, हर 1 के निर्देशांक)

2. इस सूची में प्रत्येक बिंदु के लिए:

   1. लूप इस बिंदु से Y अक्ष नीचे जब तक आप एक अवांछित बिंदु मारा (एक 0)
   2. सही एक्स अक्ष के साथ लूप जब तक आप एक एक्स समन्वय जो बिंदु के बीच किसी भी Y मूल्य पर एक 0 है मारा और न खत्म होने वाली Y समन्वय आपने चरण 1
   3. से मिला जोड़े आयत तुम सिर्फ आयतों
   की सूची में पाया
   4. मूल सूची से आयत में हर बिंदु को हटा दें।

शायद यह ऐसा करने के लिए सबसे तेज़ तरीका नहीं है, लेकिन यह काम करना चाहिए।