One for the algorithm fanatics..

[Karlos]

Hi,

Blimey, it feels a long time since I posted here. Can't have been more than a month though, right?

/me seeks reassuance :-)

Anyhow, I have this interesting puzzle to solve. I have googled a fair bit for it already but to no real avail...

Imagine I have a list of rectangles, defined in no particular order (just the order they were added to said list). These rectangles may overlap or not.

What I want to find is an algorithm that can process this list into a new list containing the minimum number of non-overlapping rectangles that cover the same shape/area as the original list did.

The process needs to be reasonably fast as the data generated isn't likely to be reused much.

In case anybody is wondering why I want this, an example useage is a layered graphical application.
The basic idea is that the original rectangle list represents graphical layers that are blended together onto a larger canvas layer. Each of these layers would simply be a buffer in normal memory.

Creating the visual preview of the canvas after all of the layers have been rendered into it involves converting it into the device dependent pixel format whilst copying it to VRAM. Typically the copy to vram is very slow. So rather than copy the whole canvas, copy only the changed area.

However, using the original rectangle list to do this would involve copying some areas (those that come from overlapped regions) to VRAM several times, which is a total waste of bandwidth. Hence the desire to process the list to give a new one that does not contain any overlap. This minimises the upload time when generating the preview.

One algorithm I've already tested is the common 2D BSP. This works fine in that it eliminates overlap by carving the total list up into non overlapping rectangles. However, it takes some time to generate and also has a habit of producing a large number of small rectangles. This tends to impact on performance almost as badly as not bothering to eliminate the overlap in the first place (except for large areas) - even non overlapping rectangles are split in many cases (since the splitting lines used are the always the edges of all the rectangles).

So, the ideal algorithm would produce the smallest number of non-overlapping rectangular areas, preferring horizontal spans over vertical.

Any ideas?

[Karlos]

Hi Volmer,

Yes, you understand the problem exactly - I want the output list to consist of as few non-overlapping rectangles as possible that describe the same shape as the original did.

This implies that if the original list contains no overlapping rectangles, the output list will be pretty much the same (although the order may be different, of course).

A simple case would be as follows:

Input List:

Rectangle 1 TopLeft = 10, 10; BotRight = 90, 50
Rectangle 2 TopLeft = 10, 30; BotRight = 90, 70

The ideal algorithm would actually generate a single rectangle from the above list with TopLeft = 10, 10 and BotRight = 90,70.

Now imagine a slightly different inpuit list

Rectangle 1 TopLeft = 10, 10; BotRight = 90, 50
Rectangle 2 TopLeft = 20, 30; BotRight = 100, 70

The same algorithm would generate 3 rectangles by splitting at the overlap:

Rectangle 1' TopLeft = 10, 10; botRight = 90, 30
Rectangle 2' TopLeft = 10, 30; botRight = 100, 50
Rectangle 3' TopLeft = 50, 30; botRight = 100, 70

I've scribbled a few ideas down also but I cant find anything that doesnt require each rectangle to be tested against the others and hence have O(n*n) complexity...