-2

I need an algorithm that, from a 1bit 2D image (a 2D matrix of mixed 1s and 0s) returns me rectangles (with the x,y coordinates of each corner) that packs the pixels that are equal to zero, using the least amount of boxes.

So for an image like

0000000
1111111
1111111
1111110
1111100
0000000

It would return something like

Rectangle 1 ((0,0),(0,1),(7,0),(7,1))
Rectangle 2 ((6,3),(7,3),(7,4),(6,4))
Rectangle 3 ((5,4),(7,4),(7,6),(5,6))
Rectangle 4 ((0,5),(0,6),(7,6),(7,5))

I feel this algorithm exists, but I am unable to Google it or name it.

eri0o
  • 2,285
  • 4
  • 27
  • 43
  • It is called set cover problem. It is NP-complete, meaning that there are no algorithm that solve it within a reasonable amount of time. There is a variety of approximate algorithms, even machine learning techniques were developed... good luck with your search. – ALX23z Sep 01 '19 at 12:49
  • (One application for something *very* similar is in [logic circuit minimisation](https://en.m.wikipedia.org/wiki/Karnaugh-Veitch_diagram).) – greybeard Sep 01 '19 at 16:08

2 Answers2

1

I'm guessing you're looking to make a compression algorithm for your images. There isn't an algorithm that guarantees the minimum number of rectangles, as far as I'm aware.

The first thing that comes to mind is taking your pixel data as a 1D array and using run-length encoding to compress it. Images tend to have rather large groupings of similarly-colored pixels, so this should give you some data savings.

There are some things you can do on top of that to further increase the information density:

  • Like you suggested, start off with an image that is completely white and only store black pixels
  • If encoding time isn't an issue, run your encoding on both white and black pixels, then store whichever requires less data and use one bit to store whether the image should start with a black or a white background.

There are some algorithms that try to do this in two dimensions, but this seems to be quite a bit more complex. Here's one attempt I found on the topic: https://pdfs.semanticscholar.org/d09a/62ea3472352bf7bbe873677cd81f348206cc.pdf

ImSimplyAnna
  • 46
  • 2
  • Uhm, now I noticed I should have specified the use case. I want to draw in a paint app a game level and then generate the blocks from the pixels that are going to be fed into a physics engine. I will take a look in the suggested algorithm. – eri0o Sep 01 '19 at 13:29
0

I found more interesting SO answers:

I also read on Covering rectilinear polygons with axis-parallel rectangles.

I even found a code here: https://github.com/codecombat/codecombat/blob/6009df26de7c7938c0af2122ffba72c07123d172/app/lib/world/world_utils.coffee#L94-L148

I tested multiple approaches but in the end none were as fast as I needed or generated a reasonable amount of rectangles. So for now I went with a different approach.

eri0o
  • 2,285
  • 4
  • 27
  • 43