Finding free non-intersecting rectangle shaped areas between rectangles in C#

Question

I have a following problem. A large rectangle contains smaller non-intersecting rectangles (The black rectangles in the picture below) and I need to find an algorithm to fill remaining free area with non-intersecting rectangles(red ones in the picture below). Speed is not an issue for the algorithm. Also if someone would have an example source code of the algorithm I would really appreciate that.

Edit. Small clarification I need to get the coordinates of the red rectangles not to draw them. I am also working with point data not images.

http://koti.mbnet.fi/niempi2/Squares.gif

Answer 1

Like most bin-packing problems this one looks like an NP-hard problem to me. With 2 rectangles, there are 8! (= 40320) possible arrangements you need to consider. Three rectangles produces 12! possibilities, a cool 480 million.

You'll need an heuristic to make this computable. Beyond favoring the outer edges of the rectangles closest to the bounding rectangle, I don't see a good one. You'd need tighter requirements on the resulting rectangles you accept, the number of them isn't going to help. Glad this is not my problem :)

Answer 2

Although there are multiple possible solutions, I think you can get to one fairly easily.

I would work in increasing values along one axis. By scanning all rectangles and ordering their edge's appearances along that axis, you could walk through them and create rectangles as you go. Each time you hit a new pair of corners, you can compare with the rectangles you currently have 'open' and determine what to do (close them, start new, divide, etc).

That statement isn't a complete solution, but I think it gets you from a complex solution to a simple one. It also doesn't seem to be NP complete in terms of performance. You might even be able to get O(n) perf.

An interesting problem. Let us know how you get on.