找到你要的答案

Q:what algorithm or approach for placing rectangles without overlapp

Q:什么样的算法或方法将矩形无叠加

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?

我有一个大长方形的大小12 * 12。现在我有6个矩形已经放置在地板上的矩形。我知道那个预置模块的中心坐标。现在我已经有了14个矩形来放置在那个矩形的地板上。怎么办呢?

在这里,我所有的预放块有中心坐标为(2,5)说,(5,7),(2),(7,8),(11),(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?

answer1: 回答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.

如果一个漂亮的布局是重要的,我建议你看看模拟力为基础的图形布局。在这个问题上,你将使用模拟力推动矩形分开,也远离边界矩形根据库仑定律。初始配置是随机选择的。你想给矩形质量成正比的面积,我认为。你没有任何弹簧力由于边缘,这使得它更容易。迭代求解运动微分方程在Matlab会很容易。或者可能有一个工具包为你做。这些算法的动画很有趣。

不幸的是,这样的约束问题,固定的矩形可以形成障碍,防止移动矩形从一个非重叠的解决方案。(考虑到固定矩形在中间的一条线上,所有的移动矩形在一边或另一边被“困住”。同样的事情发生在图布局,如果某些节点有固定的位置)有各种策略,以克服这些坏的情况下。一个是从没有固定的物体开始,让移动矩形达到平衡,然后添加固定的一个一次,最大的第一次,让系统恢复平衡每一次。另一个更简单的方法是从不同的随机初始条件开始,直到找到一个可行的。也有类似的方法模拟退火,这是一个太大的话题来讨论这里。

answer2: 回答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

这里是一个函数来检查重叠的两个矩形。你可以循环检查更多基于@ Dov的想法的矩形。

两矩形RI,i = 1,2,(xi,yi)与中心的一半长度两侧AI,BI >;0(假定边与坐标轴对齐的)。

下面是基于上述方程的实现:

在我的代码,我已经xcposition和ycposition为矩形的中心位置。

长度和宽度是矩形的边的大小。

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

你也可以使用PI值了解程度的重叠或不重叠

循环的伪代码会是这样的:

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
answer3: 回答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.

用这么小的数字,把每个矩形放在一个列表中。每次添加新的矩形时,请确保新的矩形与现有的矩形不重叠。

这是O(N 2 3),所以如果你计划增加到10个或更多的矩形,你将需要一个更好的算法,但否则你很好。

如果你的问题说明你可能无法适应它们,那么你将不得不走回头路,继续尝试不同的地方。那是一个n!问题,但是如果你有很多的开放空间,很多解决方案是可能的。

algorithm  matlab