algorithm - Finding Contiguous Areas of Bits in 2D Bit Array -

the problem

i have bit array represents 2-dimensional "map" of "tiles". image provides graphical example of bits in bit array:

i need determine how many contiguous "areas" of bits exist in array. in example above, there 2 such contiguous "areas", illustrated here:

tiles must located directly n, s, e or w of tile considered "contiguous". diagonally-touching tiles not count.

what i've got far

because these bit arrays can become relatively large (several mb in size), have intentionally avoided using sort of recursion in algorithm.

the pseudo-code follows:

let s source data array let c array of identical length source data used track "checked" bits foreach index in s     if c[i]          continue      else         set c[i]         if s[i]             extract_area(s, c, i)  extract_area(s, c, i):     let t target data array storing bits of area we're extracting     let f stack of tiles search next     push unto f     set t[i]     while f not empty         let x = pop f         if c[x]              continue         else             set c[x]             if s[x]                 push tile north of x f                 push tile south of x f                 push tile west of x f                 push tile east of x f                 set t[x]     return t 

what don't solution

• just run, requires 2 times memory of bitmap array it's processing.
• while extracting "area", uses 3 times memory of bitmap array.
• duplicates exist in "tiles check" stack - seems ugly, not worth avoiding way have things now.

what i'd see

• better memory profile
• faster handling of large areas

---

solution / follow-up

i re-wrote solution explore edges (per @hatchet 's suggestion).

this simple implement - , eliminated need keep track of "visited tiles" completely.

based on 3 simple rules, can traverse edges, track min/max x & y values, , complete when i've arrived @ start again.

here's demo 3 rules used:

one approach perimeter walk. given starting point anywhere along edge of shape, remember point.

start bounding box point.

walk perimeter using clockwise rule set - if point used current point above, first right, down, left find next point on shape perimeter. kind of simple strategy of solving maze continuously follow wall , bear right.

each time visit new perimeter point, expand bounding box if new point outside (i.e. keep track of min , max x , y.

continue until starting point reached.

cons: if shape has lots of single pixel 'filaments', you'll revisiting them walk comes back.

pros: if shape has large expanses of internal occupied space, never have visit them or record them if recording visited pixels in flood fill.

so, conserves space, in cases @ expense of time.

edit

as case, problem known, named, , has multiple algorithmic solutions. problem described called minimum bounding rectangle. 1 way solve using contour tracing. method described above in class, , called moore-neighbor tracing or radial sweep. links i've included them discuss them in detail , point out problem hadn't caught. you'll revisit start point before have traversed entire perimeter. if start point instance somewhere along single pixel 'filament', revisit before you're done, , unless consider possibility, you'll stop prematurely. website linked talks ways address stopping problem. other pages @ website talk 2 other algorithms: square tracing, , theo pavlidis's algorithm. 1 thing note these consider diagonals contiguous, whereas don't, should can handled minor modifications basic algorithms.

an alternative approach problem connected-component labeling. needs though, may more time expensive solution require.

additional resource:

moore neighbor contour tracing algorithm in c++