Jak skutecznie znaleźć obszary w tablicy dwuwymiarowej?

Question

Potrzebuję pomysłu, jak skutecznie znaleźć obszary poniżej oznaczone jako 0 w dwuwymiarowej tablicy. Należy zauważyć, że istnieją inne obszary, takie jak to zdjęcie pokazuje jeden z dwóch, którzy posiadają współrzędne (0.0), a druga posiada współrzędne (21.3).

00000000000111110000111 
00000000001111110000111 
00000000011111100000111 
00000000000111000001101 
00000000011100000011101 
00000001111100001111001 
00000111111111011111001 
00000001111100001111001 
00000000010000000011001 
00000000000000000001111 

Oczywiście prawdziwa tablica będzie znacznie większa. Wersja rekurencyjna, która przechodzi na wszystkie strony i zatrzymuje się przy znaku 1 lub tablicy, nie jest wystarczająco szybki.

Answer 1

Wygląda na to, że szukasz flood-fill algorithm. Strona wikipedii, którą połączę, wymienia kilka algorytmów, które mogą być szybsze od oczywistej metody rekurencyjnej.

Wypełnienie dobrze pasuje, jeśli szukane obszary są niewielkie w porównaniu z całą tablicą i nie trzeba ich wyszukiwać pod , wszystkich. Jeśli chcesz wiedzieć o większości lub wszystkich z nich, to lepszym rozwiązaniem będzie obliczenie ich wszystkich w jednym ujęciu za pomocą algorytmu opartego na scalaniu connected component labeling. Oto niektóre kodu, który implementuje taki algorytm (zauważ, że mam zmieniony go uruchomić w jednym przejściu):

#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <vector> 
#include <map> 

const char *data[] = { 
"00000000000111110000111", 
"00000000001111110000111", 
"00000000011111100000111", 
"00000000000111000001101", 
"00000000011100000011101", 
"00000001111100001111001", 
"00000111111111111111001", 
"00000001111100001111001", 
"00000000010000000011001", 
"00000000000000000001111", 
NULL 
}; 

struct label { 
private: 
    int index; 
    int rank; 
    label *parent; 
public: 
    label() 
     : index(-1), rank(0), parent(this) 
    { } 

    int getIndex(int &maxIndex) { 
     if (parent != this) 
      return find()->getIndex(maxIndex); 

     if (index < 0) 
      index = maxIndex++; 
     return index; 
    } 

    label *find() { 
     if (parent == this) 
      return this; 

     parent = parent->find(); 
     return parent; 
    } 

    label *merge(label *other) 
    { 
     label *xRoot = find(); 
     label *yRoot = other->find(); 

     if (xRoot == yRoot) 
      return xRoot; 

     if (xRoot->rank > yRoot->rank) { 
      yRoot->parent = xRoot; 
      return xRoot; 
     } else { 
      xRoot->parent = yRoot; 
      if (xRoot->rank == yRoot->rank) 
       yRoot->rank++; 
      return yRoot; 
     } 
    } 
}; 

int width, height; 

int main() { 
    for (int i = 0; data[0][i]; i++) 
     width = i + 1; 
    for (int i = 0; data[i]; i++) { 
     height = i + 1; 
    } 

    std::vector<std::vector<unsigned short> > lblinfo; 
    lblinfo.resize(height, std::vector<unsigned short>(width, 0)); 

    std::vector<label *> labels; 
    labels.push_back(NULL); // 0 is used as an unassigned flag 

    for (int y = 0; y < height; y++) { 
     for (int x = 0; x < width; x++) { 
      if (data[y][x] == '1') 
       continue; 

      // Try to find a neighboring label 
      unsigned short lblid = 0; 
      if (x != 0 && lblinfo[y][x-1] != 0) 
       lblid = lblinfo[y][x-1]; 

      // merge with cells above 
      if (y != 0) { 
       for (int x2 = x - 1; x2 <= x + 1; x2++) { 
        if (x2 < 0) 
         continue; 
        if (x2 >= width) 
         continue; 

        unsigned short otherid = lblinfo[y - 1][x2]; 
        if (!otherid) 
         continue; 

        if (!lblid) 
         lblid = otherid; 
        else { 
         labels[lblid]->merge(labels[otherid]); 
        } 
       } 
      } 

      if (!lblid) { 
       // assign a new label 
       lblid = labels.size(); 
       labels.push_back(new label); 
      } 
      lblinfo[y][x] = lblid; 
     } 
    } 

    // Assign indices to the labels by set and print the resulting sets 
    int maxindex = 0; 
    static const char chars[] = "abcefghijklmnopqrstuvwxyz"; 
    for (int y = 0; y < height; y++) { 
     for (int x = 0; x < width; x++) { 
      unsigned short labelid = lblinfo[y][x]; 
      if (labelid == 0) { 
       putchar(data[y][x]); 
       continue; 
      } 

      label *label = labels[labelid]; 
      int idx = label->getIndex(maxindex); 
      if (idx >= sizeof(chars) - 1) { 
       printf("\n\n Too many labels to print!\n"); 
       exit(1); 
      } 

      putchar(chars[idx]); 
     } 
     printf("\n"); 
    } 

    return 0; 
}