3

I'm looking for a way to convert a 2D array to the fewest possible rectangles like in this example:

       X
    12345678
    --------
  1|00000000
  2|00011100
  3|00111000
Y 4|00111000
  5|00111000
  6|00000000

to the corner coordinates of the rectangles:

following the (x1,y1);(x2;y2) template

rectangle #1 (4,2);(6,2)
rectangle #2 (3,3);(5,5)

There has been a similar question here before but unfortunately, the link provided in its answer is broken, and I cannot check it anymore.

I'd like to do this in C# but any kind of help is appreciated.

(It doesn't even have to be the fewest possible rectangles, but the fewer the better :) )

Thanks in advance!

Be Brave Be Like Ukraine
  • 7,596
  • 3
  • 42
  • 66
theAdam
  • 65
  • 12
  • There's no obvious relationship here between the two representations. Would you elaborate? – casperOne Sep 30 '12 at 01:16
  • I've edited the OP, I hope it's more understandable now, sorry for the confusion. – theAdam Sep 30 '12 at 01:20
  • How can two points form a rectangle? I know you are trying to say something obvious there, but it is not intuitive. – swiftgp Sep 30 '12 at 01:25
  • Two points can define a rectangle if you use them points as the opposing cornerpoints of the rectangle. I used XY template, and I edited it in for easier understanding. – theAdam Sep 30 '12 at 01:47
  • 1
    I guess [this Q](http://stackoverflow.com/questions/2628118/rectangles-covering) is what you need. The image has been lost, but you may refer to a [previous edit](http://stackoverflow.com/revisions/2628118/3) to see the original request. And the answers seem to be very compelling. – Be Brave Be Like Ukraine Sep 30 '12 at 01:52
  • Thanks, I'm checking it out now! – theAdam Sep 30 '12 at 01:58

2 Answers2

2

I think that you are trying to cover a set of points in the 2D plane with the minimum required number of rectangles. An answer to Find k rectangles so that they cover the maximum number of points said that this was an NP-complete problem and linked to here (which works for me). A google search finds http://2011.cccg.ca/PDFschedule/papers/paper102.pdf.

There papers agree that rectangle covering is NP-complete but do not actually prove it, and the references for this seem to be unusually elusive - https://cstheory.stackexchange.com/questions/3957/prove-that-the-problem-of-rectilinear-picture-compression-is-np-complete

What I take from these documents is this:

  1. It is unlikely that there is an affordable way of getting the absolutely best answer for large problems, so you might have to either spend a lot of time to get exact answers for problems that are in some sense small, by exhausting over all possible alternatives or perhaps using something like branch and bound, or settle for affordable methods - like greedy search, or beam search, or limited discrepancy search - which are not guaranteed to give you the absolutely best answer.

  2. In this case there seem to be more restricted versions of this problem which are not NP-complete. You might possibly read a paper and find that there is some detail of your problem that means that this method applies to you. One example is "AN ALGORITHM FOR CONSTRUCTING REGIONS WITH RECTANGLES: INDEPENDENCE AND MINIMUM GENERATING SETS FOR COLLECTIONS OF INTERVALS*" by Franzblau and Kleitman - I found this in the ACM Digital Library, though - I don't know if it is generally accessible. It works for a restricted set of polygons.

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • Yes, this roughly defines my problem, but after a quick look into these documents, they don't really provide an algorithmic method to solve the problem itself (at least none that I can understand and reproduce in C#). Thanks though, I'll be sure to read them anyway and see if I can make out something. – theAdam Sep 30 '12 at 10:57
  • I have edited in my comment on the relevance of these papers - which is mostly my usual reaction to finding that something is NP-complete. – mcdowella Sep 30 '12 at 11:21
  • Thank you, I think I will go with a self-written optimisation then, possibly check for rectangles that have 1 as height, so as I cycle through the array, it will check for continous lines. – theAdam Sep 30 '12 at 11:56
-1

This may help you get started. If you convert the binary data to numbers, you get this:

0
28
56
56
56
0

So where ever there are consecutive equal numbers, there is a rectangle.

Steve Wellens
  • 20,506
  • 2
  • 28
  • 69