Board index » delphi » Dirty Rectangle Algorithm Explained

Dirty Rectangle Algorithm Explained

I have a matrix that represents the changes between two similar
images; a one (1) represents a change between the images and a
zero (0) represents no change.

I need an algorithm that will return a number of rectangles that
cover all the changes (1's) in the matrix.  The rectangles should be
non-overlapping.  Zeros can be contained in rectangles, though
hopefully the number of zeros in a rectangle will be less than the
ones by a large margin.

I basically looking for any algorithm to start with...speed is not of
the essence.

If anyone can help in locating such an algorithm, I would be
appreciative.

Thanks,

Michael Heacock
Michael Heacock
cere...@islandnet.com

 

Re:Dirty Rectangle Algorithm Explained


Quote
>I basically looking for any algorithm to start with...speed is not of
>the essence.

        Surely that's not what you really mean - AN algorithm would be
just to cover each 1 with its own 1x1 rectangle.

--
David Ullrich
Don't you guys find it tedious typing the same thing
after your signature each time you post something?
I know I do, but when in Rome...

Re:Dirty Rectangle Algorithm Explained


Quote
Michael Heacock (cere...@islandnet.com) wrote:

: I have a matrix that represents the changes between two similar
: images; a one (1) represents a change between the images and a
: zero (0) represents no change.

: I need an algorithm that will return a number of rectangles that
: cover all the changes (1's) in the matrix.  The rectangles should be
: non-overlapping.  Zeros can be contained in rectangles, though
: hopefully the number of zeros in a rectangle will be less than the
: ones by a large margin.

The dirty rectangle algorithm I use in a sprites animation app I am
working on stores the dirty rectangles as a linked list of RECT
structures.  Prior to blitting rectangles to the screen, I merge
the list, which is what I assume you want to do.  I suppose you
can adapt this technique to your matrix method of keeping track of
dirty rects.

while (!done) {
        Found = False;
        for each item in the list {
                for each other item in the list {
                        if the rects intersect {
                                merge them into a bigger rect
                                Found = True
                        }
                }
        }
        if Found still equals false, we're done.

Quote
}

--
------------------------
-- David Kirkpatrick  --
-- Southwest Software --
-- dav...@csn.org     --

Re:Dirty Rectangle Algorithm Explained


Quote
> I need an algorithm that will return a number of rectangles that
> cover all the changes (1's) in the matrix.  The rectangles should be
> non-overlapping.  Zeros can be contained in rectangles, though
> hopefully the number of zeros in a rectangle will be less than the
> ones by a large margin.

First time I read this I missed the bit about non-overlapping.

One strategy that occurred to me was to base an algorithm on the game of
Life. (You know, where cells on a board change black-to--white depending
on the state of the neighbours.)

If for each cell, you counted up the number of adjacent neighbours,
(ignore diagonals), and then make any 0-cell that had more than one
neighbour a 1-cell, this would kind of do what you want.

You would have to call this repeatedly, until things stopped changing.
You would then have a large grid, of 0's with solid blocks of 1's in it.
You would then need to search through and detect these blocks and get
back the rectangle coordinates. But that should be fairly easy.

I don't think this would be a very good algorithm, I just thought it was
quite a fun approach. It might be feasible, if you could avoid doing
every cell on every pass of the algorithm. That would mean on each pass,
tracking the areas that were still changing, and only redoing those.

I didn't bother mentioning it earlier, because it can't produce
overlapping rectangles. If two rectangles overlap, or touch at a corner,
it will fill them out to one larger rectangle.

----------------------------------------
Nick Moon  ncm...@cix.compulink.co.uk
----------------------------------------

Other Threads