1

I have a pre-defined-size rectangular area with some other rectangles inside, which represents filled regions, or, let say, obstacles.

All the rectangles are axis-aligned. Origin of the axis (i.e. 0,0) is top-left. The X and Y coordinates of all the rectangles, as well as the horizontal and vertical size is known.

Information about the rectangles inside the main area is contained in an already-sorted array, where i[0],i[1] are the X,Y coordinates of the upper-left corner and i[2],i[3] are respectively the x and y size:

[
    [10,1,14,7],
    [34,1,14,15],
    [16,22,27,44]
]

How can i get all the rectangles covering the free remaining space, like in the image below?

(credits: Jukka Jylänki, A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing http://clb.demon.fi/)

enter image description here

I don't need an algorithm for optimal bin-packing, as the rectangles are already placed, nor to find the biggest rectangle, but i'm aware that these can be related arguments.

I have also read some papers about the line-sweep algorithm, but i'm not able to get a working implementation, and so i cannot imagine if this would be the right solution for my problem.

My first attempt (clearly wrong) was to gather all the cuts generated by all the sides (inverse intersection):

[
    [24,8,37,8],
    [1,16,60,6],
    [1,22,15,44],
    [43,22,18,44],
    [1,66,60,5],
    [1,1,9,70],
    [10,16,6,55],
    [24,1,10,21],
    [34,8,9,14],
    [43,8,5,63],
    [48,1,13,70]
]

...but this would require an additional step to to join adjacent rectangles and then filter out those inside a bigger one. See for example, the red-marked rectangles in this picture:

joined rectangles
Could be this a way to go, though not optimized?

deblocker
  • 7,629
  • 2
  • 24
  • 59
  • I don't know why you say 'clearly wrong' - you *have* established a set of rectangles covering the free space left by the three given rectangles. Now, if you want a 'better' solution (in whatever sense) you need to say what counts as 'better'... – AakashM Jul 21 '16 at 08:44
  • btw does http://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles?rq=1 cover you? – AakashM Jul 21 '16 at 08:57
  • @AakashM: i would not talk of a "better" solution - i 'm not able to get the *right* solution, which is the one in the picture of Jukka. For example, in the question referenced by you, this would be [C1,C3],[A2,C3],[A2,B4] – deblocker Jul 21 '16 at 09:35
  • 1
    Ah OK you want covering rather than partitioning. – AakashM Jul 21 '16 at 10:47

0 Answers0