what algorithm or approach for placing rectangles without overlapp

Question

I have a big rectangle of size 12*12. Now I have 6 rectangles already placed on the floor of that rectangle. I know the center coordinate of that pre-placed module. Now I have few another 14 rectangles to place upon that floor of that rectangle. How to do so?

here all my pre placed block those having center coordinate as say (2,5),(5,7),(9,2),(7,8),(11,9),(3,11).

Now how could I place 14 another rectangle in this floor so that it would not over lap with any preplaced block. I would like to code in MATLAB..but what approach should I follow?

Answer 1

If a nice even placement is important, I suggest you look up simulated force-based graph layout. In this problem, you'll use simulated forces pushing the rectangles apart and also away from the border rectangle according to Coulomb's law. The initial configuration is randomly selected. You'll want to give the rectangles mass proportional to their area, I think. You don't have any spring forces due to edges, which makes it easier. The iteration to solve the differential equations of motion will be easy in Matlab. Or there may well be a toolkit to do it for you. Animations of these algorithms are fun.

Unfortunately with constrained problems like this, the fixed rectangles can form barriers that prevent the moving rectangles from getting to a non-overlapping solution. (Think of the case where the fixed rectangles are in a line down the middle and all the moving ones get "trapped" on one side or the other. The same thing happens in graph layout if some nodes have fixed locations.) There are various strategies for overcoming these bad cases. One is to start with no fixed objects at all, let the moving rectangles come to an equilibrium, then add the fixed ones one at a time, largest first, allowing the system regain equilibrium each time. Another, simpler one is just to start from different random initial conditions until you find one that works. There are also approaches related to simulated annealing, which is too big a topic to discuss here.

Answer 2

Here is a function to check overlap for two rectangles. you could loop it to check for more number of rectangles based on @Dov's idea.

For two rectangles Ri, i = 1,2, with centers (xi,yi) and half-lengths of their sides ai,bi > 0 (assuming that the sides are aligned with the coordinate axes).

Here is my implementation based on above equation:

In my code i've taken xcPosition and ycPosition as the center position of the rectangle.

Also length and breadth are the magnitude of sides of the rectangle.

function [ overLap, pivalue ] = checkOverlap( xcPosition1,ycPosition1,xcPosition2,ycPosition2,length1,breadth1,length2,breadth2 )

pix = max((xcPosition2 - xcPosition1 -(length1/2)-(length2/2)),(xcPosition1 -xcPosition2 -(length2/2)-(length1/2)));
piy = max((ycPosition2 - ycPosition1 -(breadth1/2)-(breadth2/2)),(ycPosition1 -ycPosition2 -(breadth2/2)-(breadth1/2))); 
pivalue = max(pix, piy); 

if (pivalue < 0)
    overLap = 1;  %// Overlap exists 
else
    overLap = 0;  %// No overlap
end
end

You could also use the pivalue to know the degree of overlap or Non-overlap

The Pseudo-code for looping would be something like this:

for i = 1 : 14
    for j = 1 : i-1 + 6 already placed parts
        %// check for overlap using the above function here
        %// place the part if there is no overlap
    end
end

Answer 3

With such a small number, put each rectangle in a list. Each time you add a new rectangle, make sure the new one does not overlap with any of the existing ones.

This is O(n^2), so if you plan to increase to 10^3 or more rectangles you will need a better algorithm, but otherwise you're fine.

Now if your problem specifies that you might not be able to fit them all, then you will have to backtrack and keep trying different places. That is an N! problem, but if you have a lot of open space, many solutions will be possible.