a compression/packing problem

Question

Hi everyone, I have a problem: Given an array nxm that contains 0's or 1's, I need group the 0 values into rectangles. At the beginning, I was used a simple quadtree, but different nodes in the same level of the tree have the same value. I'm not totally sure if the R-tree works for my problem or another data structure because I just will use this structure in pre-calculate step and that's it. Thanks in advanced

p.d.: I'm working with 2D images

esmitt

Answer 1

i would opt for a recursive solution. something along the lines of

iszeroes returns 1 if matrix has only zeroes
def search_for_zeroes(matrix, colormatrix)
!   conquer - part, matrix is essentially only a cell   
    if size(matrix) .eq. 1 then 
        search_for_zeroes = iszeroes(matrix)
        if iszeroes(colormatrix(matrix)then 
            colormatrix(matrix) = black) 
        end if  
    end if
!   divide - part, looks if four cells are all zero and colors them black
    if search_for_zeroes(upper_left) and search_for_zeroes(upper_right) 
        and search_for_zeroes(lower_left) and search_for_zeroes(lower_right) then
        search_for_zeroes = true
        colormatrix(matrix) = black         
    end if

i have not coded it myself, just pseudocode. will change it when i get off work today, but this should work too. cheers