1

Consider the 3 rectangles stored as 2 opposing corners.

$ r_1 = (0,0,2,1)$ , $ r_2 = (1,1,2,2)$ , $ r_3 = (2,0,3,1)$

The area covered by these 3 rectangles can be represented using 2 rectangles

$ r_4 = (0,0,3,1)$, $ r_5 = (1,1,2,2) $

Is there algorithm that can take in a list of smaller rectangles and consolidate them into larger rectangles that cover the same area? (the goal is to minimise the number of rectangles being stored)

harder example:

small rects: $ r_1 = (0,0,2,2)$ , $ r_2 = (0,2,1,4)$ , $ r_3 = (1,2,2,3)$

potential solution: $ r_4 = (0,0,2,3)$ , $ r_5 = (0,3,1,4)$

This one is more complicated because there is no trivial merges where the edges of 2 rectangles are 'perfectly adjacent'(i dont know the proper terminology) ie. the edge 2,0,2,1 in the first example is common to $r_1$ and $r_3$

Rishab Sharma
  • 11
  • In your example two of the rectangles share an edge. Any such pair can always be merged. Can you edit the question to give us an example where that strategy doesn't optimize? In your example the rectangles are disjoint. Will that always be the case? More examples, please. – Ethan Bolker Feb 28 '18 at 00:40
  • Is this for an application? (For instance, are you trying to make a texture atlas?) – Milo Brandt Feb 28 '18 at 00:55
  • I added a more complex example . It is a bit more complicated because the solutions require splitting the rectangles into smaller rectangles and then performing merges where possible. Maybe that is one possible way of doing it? @MiloBrandt nope not making a texture atlas. I need to store rectangles in on disk and am trying to reduce the amount of storage used. – Rishab Sharma Feb 28 '18 at 00:57

1 Answers1

0

I think section 6 of this paper has a pretty good solution to my problem. I think this question can be closed. https://pdfs.semanticscholar.org/d4ee/f45c3e96a7df047c43e5b1c25b62898aec01.pdf

Rishab Sharma
  • 11