Return to Question

I already have a working algorithm for this but it's home-made and there is some redundancy in the things it checks, so I'm looking for a fast algorithm (or the name of it) that would detect undrawn portions of a 2d map (a picture or a grid), returning those portions as a list of Rectangles which borders are parallel to the axis (x, y, width, height). The map is not very big, like 200x200.

Edit: Rectangles to detect have to be parallel to the axis x and y

For instance ran on this map and looking for space character " " and for 2x3 rectangles :

*C***DDD****
*01F  *E*  *
***   ***  *
**    *    *
*A****  ****
************

It would detect the portions marked with "X":

*C***DDD****
*01FXX*E*XX*
*** XX***XX*
**  XX*  XX*
*A****  ****
************

Has anyone heard of one?

The detection doesn't have to be exact (it's ok if some areas are not detected, but most need to be). It should be very fast. I think some bitmap compression algorithm like PNG ought to use that kind of detection, but I'm not sure. Thanks in advance.

I already have a working algorithm for this but it's home-made and there is some redundancy in the things it checks, so I'm looking for a fast algorithm (or the name of it) that would detect undrawn portions of a 2d map (a picture or a grid), returning those portions as a list of Rectangles which borders are parallel to the axis (x, y, width, height). The map is not very big, like 200x200.

Edit: Rectangles to detect have to be parallel to the axis x and y

For instance ran on this map and looking for space character " " and for 2x3 rectangles :

*C***DDD****
*01F  *E*  *
***   ***  *
**    *    *
*A****  ****
************

It would detect the portions marked with "X":

*C***DDD****
*01FXX*E*XX*
*** XX***XX*
**  XX*  XX*
*A****  ****
************

Has anyone heard of one algorithm like this, but fast? Right now what I'm doing is that I'm scanning through each cell and checking if the w*h Rect at current position is filled with the search value. However you can see there is a lot of redundancy there.

I wonder if some bitmap compression algorithm like PNG don't use that kind of detection, so as to compress repetitions of tiles/uniform areas. If that's the case that should be very fast algorithm they use because speed is an issue for them.

The detection doesn't have to be exact (it's ok if some areas are not detected, but most need to be). So mostly it needs to be very fast.

I'll go and write a slow working boilerplate for this now, but I'm looking for a quick algorithm that would detect undrawn portions of a map, returning those portions as a list of Rectangle coordinates (x, y, width, height). The map is not very big, like 200x200. Has anyone heard of one like this?

The detection doesn't have to be exact (it's ok if some areas are not detected), so mostly I'm looking for speed. Thanks in advance for any suggestion!

I already have a working algorithm for this but it's home-made and there is some redundancy in the things it checks, so I'm looking for a fast algorithm (or the name of it) that would detect undrawn portions of a 2d map (a picture or a grid), returning those portions as a list of Rectangles which borders are parallel to the axis (x, y, width, height). The map is not very big, like 200x200.

Edit: Rectangles to detect have to be parallel to the axis x and y

For instance ran on this map and looking for space character " " and for 2x3 rectangles :

*C***DDD****
*01F  *E*  *
***   ***  *
**    *    *
*A****  ****
************

It would detect the portions marked with "X":

*C***DDD****
*01FXX*E*XX*
*** XX***XX*
**  XX*  XX*
*A****  ****
************

Has anyone heard of one?

The detection doesn't have to be exact (it's ok if some areas are not detected, but most need to be). It should be very fast. I think some bitmap compression algorithm like PNG ought to use that kind of detection, but I'm not sure. Thanks in advance.