Finding rectangles with at least n spots inside

[GNiewerth]

Hi everyone,

I´m facing this problem:

I´ve got a white bitmap on which black spots are randomly distributed. Now I have to find all possible rectangles (fixed width X/height Y) that contain at least N black spots.
Here´s my approach, without having written any code yet:

1) Start with the topmost topleft spot as reference

2) Expand a double-width single-height rectangle (2X/Y) downwards so that the spot is on the middle of the top edge of that rectangle.

3) Find the leftmost spot inside that rectangle

4) Expand a rectangle with width X and height Y to the left so that the top edge of the second rectangle lies on the top edge of the first rectangle. Count all spots inside the second rectangle, if they exceed the threshold remember the rectangle and the spot count.

5) pick the nearest spot to the right in the second rectangle, check if its distance to the right edge of the first rectangle is larger than X. If so, go to 4.

6) repeat 3-5 for all spots on the bitmap whose distance to the bottom of the bitmap is larger than Y.


Thanks for help,
Guido