一个算法的空间了重叠的矩形？ [英] An algorithm to space out overlapping rectangles?
问题描述
这个问题实际上与循环翻转处理，我就在下面概括为这样的：
我有一个二维视图，而我在屏幕上区域内的一些矩形。如何I S $ P $垫掉那些箱子，使它们不相互重叠，但其中只有最小的移动调整？
在矩形的立场是动态的，取决于用户的输入，所以它们的位置可能在任何地方。
附图像显示的问题和期望的解决方案。
在现实生活中的问题涉及翻车，其实。
答案在评论问题
-
矩形的大小是不固定的，并且是依赖于文字在侧翻的长度
-
关于屏幕大小，现在我认为这是最好的假设，屏幕的大小是不够的矩形。如果有太多的矩形和算法中产生的无解，那么我只需要调整的内容。
-
要求，以移动微创则多为asethetics不是一个绝对的工程要求。人们可以隔开两个矩形加入它们之间的巨大的距离，但它不会好看的图形用户界面的一部分。我们的想法是让翻转/矩形尽可能接近其来源（我将连接到源用黑线）。因此，无论是移动的只有我一个X'或'半x同时移动'是好的。
我是工作了一下，在此，我也需要类似的东西，但我已经推迟了算法的开发。你帮我弄些冲动：D
我还需要在源$ C $ C，所以在这儿呢。我的工作是在数学，但我还没有大量使用的功能特点，我想这会很容易转化为任何过程语言。
历史的角度
首先，我决定开发的算法的圈子里，因为路口是容易计算。这只是取决于中心和半径。
我能够用数学方程求解器，以及它的表现很好。
只要看看：
这是很容易。我只装有下列问题的解决者：
对于每圈
解决[
查找圆新坐标
最小化的距离的图像的几何中心的
以在帐户
中心＆GT之间的距离; R1 + R2 *所有其他各界
移动圆在其中心和之间的线
附图的几何中心
]
那么简单，因为这一点，数学做了所有的工作。
我说：哈！这很容易，现在让我们去为矩形！。可是我错了......
矩形蓝调
与矩形的主要问题是，查询的交点是一个讨厌的功能。是这样的：
所以，当我试图养活了数学有很多这样的条件公式，它的表现如此糟糕，我决定做一些程序上。
我的算法最终如下：
由几个点展开每个矩形的大小，以得到最终的配置差距
而有交点
矩形通过路口的数量排序列表
推堆栈最相交的矩形，并从列表中删除
//现在所有剩余的矩形不彼此交叉
虽然栈不空
从协议栈和流行的矩形重新将其插入到列表
找到图表的几何中心G（每次！）
找到运动矢量M（从G以矩形中心）
增量在M的方向上移动的矩形（两侧）
直到没有交集
收缩矩形到其原始尺寸
您可能注意到，最小运动条件是不完全满意（只在一个方向上）。但我发现，移动矩形在任何方向去满足它，有时会结束了一个令人困惑的地图变化的用户。
由于我设计的用户界面，我选择移动矩形远一点，但在一个更加predictable方式。您可以更改算法来检查各个角度和周围的当前位置，直到一个空的地方都半径被发现，但它会更加苛刻。
反正这些是结果的例子（前/后）：
正如您可能会看到，最小运动很不满意，但效果都不够好。
我会后在code在这里，因为我有我的SVN仓库了一些麻烦。我会删除它时，问题都解决了。
编辑：
您也可以使用 R树寻找矩形交叉点，但似乎矫枉过正来处理一个少数矩形。而且我还没有算法已经实施。也许别人可以指向你到你选择的平台上现有的实现。
警告！ code是第一种方法..不是伟大的品质着呢，肯定有一些错误。
这是数学。
（*先定义某些功能*）
清除[Global` *];
RN [X_]：= RandomReal [{0，X}];
RNR [X_]：= RandomReal [{1中，x}];
rndCol []：= RGBColor [RN [1]，RN [1]，RN [1]];
其minX [L_，I_]：=升[[Ⅰ]] [[1]] [[1]]; （*只是为了方便阅读*）
MAXX [L_，I_]：=升[[Ⅰ]] [[1]] [[2]];
MINY [L_，I_]：=升[[Ⅰ]] [[2]] [[1]];
MAXY [L_，I_]：=升[[Ⅰ]] [[2]] [[2]];
颜色[L_，我_]：= L [[i]] [[3];
intersectsQ [L_，I_，J_]：=（* L列表，（I，J）指标，
列表= {{X1，X2}，{Y1，Y2}} *）
（*一个矩形不intesect与自身*）
如果[最大[其minX [L，I]，其minX并[J]]＆LT;闵[MAXX [L，I]，MAXX并[J]]＆功放;＆安培;
最大[MINY [L，I]，MINY [升，J〕25;闵[MAXY [L，I]，MAXY并[J]]，
真假];
（*相交数的矩形*）
（*跟我一样指数*）
countIntersects [L_，I_]：=
算[表[intersectsQ [L，I，j]中，{Ĵ，1，长度[升]}]，真] -1;
（*和有R为长方形*）
countIntersectsR [L_，R_]：=（
返回[计数表[intersectsQ [追加[L，R]，长度[L] + 1，J]，
{Ĵ，1，长度[升] +1}]，真〕 - 2]）
（*获取最大路口全部矩形*）
findMaxIntesections [L_]：=最大值[表[countIntersects [L，I]
{I，1，长度[升]}]];
（*获取矩形中心*）
rectCenter [L_，I_] = {1/2（MAXX [L，I] +其minX [L，I]），
1/2（MAXY [L，I] + MINY [L，I]）};
（*获取全数字（名单的几何体中心），以审美移动*）
geometryCenter [L_]：=（* returs {X，Y} *）
平均表[rectCenter [L，I]，{我，长度[L]}]];
（*递增或DECR。大小所有rects受了一点（把/删除边框）*）
changeSize [L_，incr_]：=
表[{{其minX [L，I] - 增量，MAXX [L，I] +增量}，
{MINY [L，I] - 增量，MAXY [L，I] +增量}，
颜色[L，I]}，
{I，长度[升]}];
sortListByIntersections [L_]：=（*排序最相交Rects列表*）
模块[{A，B}，
一个= MapIndexed [{countIntersectsR并[＃1]，＃2}＆安培;,升];
B = SortBy并[a， - ＃[[1]]安培;];
返回[表[升〔并[b [[Ⅰ] [[2]] [[1]]]]，{I，长度并[b]}]];
]。
（*实用功能*）
DEB [X_]：=（打印[--------];打印[X]打印[---------]）（*调试*）
tableForPlot [L_]：=（*为绘制*）
表[{颜色[L，I]，矩形[{其minX [L，I]，MINY [L，I]}，
{MAXX [L，I]，MAXY [L，I]}]}，{我，长度[L]}];
genList [nonOverlap_，Overlap_]：=（*生成rects的初始列表*）
模块[{ALIST，blist，A，B}，
（ALIST =（*生成非重叠 - Tabuloid *）
表[{{mod[我，3]，MOD [我，3] + 0.8}，
{mod[I，4]，MOD [I，4] + 0.8}，
rndCol []}，{I，非重叠}];
blist =（*随机重叠*）
表[{{一个RNR = [3]，A + RNR [2]}，{B = RNR [3]，B + RNR [2]}，
rndCol []}，{重叠}];
返回[加入[ALIST，blist]（*加入两个*）];）
]。
主要
CLIST = genList [6,4]。 （*生成一个混合固定和放大器;随机设置*）
增量= 0.05; （*可能需要确定最佳的增量部分启发式*）
CLIST = changeSize [CLIST，增量] （*扩大rects使边界不
相互接触*）
（*现在删除所有拦截矩形，直到没有更多的交叉点*）
工作表= {}; （*栈*）
而[findMaxIntesections [CLIST]≥ 0，
（*迭代，直到没有交集*）
CLIST = sortListByIntersections [CLIST]
（*把最相交的第一个*）
prependTo [工作清单，您是第[CLIST];
（*推送工作列表与相交*）
CLIST =删除[CLIST，1]; （*和CLIST *删除它）
]。
（*有没有交集现在，让弹出堆栈*）
而[工作列表！= {}，
prependTo [CLIST，您是第[工作表];
（*推第一个元素的CLIST *前）
工作表=删除[工作列表，1];
（*从工作清单*删除它）
toMoveIndex = 1;
（*将移动最相交的矩形*）
G = geometryCenter [CLIST]
（*所以GEOM。感觉是preserved *）
vectorToMove = rectCenter [CLIST，toMoveIndex] - 克;
如果[诺姆[vectorToMove] LT; 0.01，vectorToMove = {1,1}]。 （*以防万一*）
vectorToMove = vectorToMove /规范[vectorToMove]
（*明智地管理步长*）
（*现在迭代寻找最小的移动第一种方式，那么其他*）
I = 1; （*移动量*）
尽管[countIntersects [CLIST，toMoveIndex]！= 0，
（*如果矩形仍相交*）
（*移动交替的方式（-1）^ N *）
CLIST [[toMoveIndex] [[1]] + =（-1）^二增量vectorToMove [[1]]（* X的coords *）
CLIST [[toMoveIndex] [[2]] + =（-1）^二增量vectorToMove [[2]];（* Y的coords *）
我++;
]。
]。
CLIST = changeSize [CLIST，-incr]（*恢复原来的尺寸*）;
心连心！
编辑：多角度搜索
我实现的算法，允许在各个方向进行搜索，而是由几何对称强加轴给preference发生了变化。
在以上的周期为代价的，这导致了更紧凑的最终配置，你可以在这里看到如下：
更多样本这里。
伪code主循环改为：
由几个点展开每个矩形的大小，以得到最终的配置差距
而有交点
矩形通过路口的数量排序列表
推堆栈最相交的矩形，并从列表中删除
//现在所有剩余的矩形不彼此交叉
虽然栈不空
找到图表的几何中心G（每次！）
找到preFERRED运动向量M（从G以矩形中心）
从堆栈中弹出矩形
随着矩形
虽然有交叉点（列表+矩形）
为了提高移动模
用于增加角（0，π/ 4）
旋转矢量M扩大旁边的M角
（*角度，-angle，PI +角，皮角*）
重新定位矩形accorging至M
重新插入修饰载体导入列表
收缩矩形到其原始尺寸
我不包括源$ C $ C为简便起见，只是要求它，如果你认为你可以使用它。我认为，你应该走这条路，最好切换至R树（很多在这里需要间隔测试）
This problem actually deals with roll-overs, I'll just generalized below as such:
I have a 2D view, and I have a number of rectangles within an area on the screen. How do I spread out those boxes such that they don't overlap each other, but only adjust them with minimal moving?
The rectangles' positions are dynamic and dependent on user's input, so their positions could be anywhere.
Attached images show the problem and desired solution
The real life problem deals with rollovers, actually.
Answers to the questions in the comments
Size of rectangles is not fixed, and is dependent on the length of the text in the rollover
About screen size, right now I think it's better to assume that the size of the screen is enough for the rectangles. If there is too many rectangles and the algo produces no solution, then I just have to tweak the content.
The requirement to 'move minimally' is more for asethetics than an absolute engineering requirement. One could space out two rectangles by adding a vast distance between them, but it won't look good as part of the GUI. The idea is to get the rollover/rectangle as close as to its source (which I will then connect to the source with a black line). So either 'moving just one for x' or 'moving both for half x' is fine.
I was working a bit in this, as I also needed something similar, but I had delayed the algorithm development. You helped me to get some impulse :D
I also needed the source code, so here it is. I worked it out in Mathematica, but as I haven't used heavily the functional features, I guess it'll be easy to translate to any procedural language.
A historic perspective
First I decided to develop the algorithm for circles, because the intersection is easier to calculate. It just depends on the centers and radii.
I was able to use the Mathematica equation solver, and it performed nicely.
Just look:
It was easy. I just loaded the solver with the following problem:
For each circle
Solve[
Find new coördinates for the circle
Minimizing the distance to the geometric center of the image
Taking in account that
Distance between centers > R1+R2 *for all other circles
Move the circle in a line between its center and the
geometric center of the drawing
]
As straightforward as that, and Mathematica did all the work.
I said "Ha! it's easy, now let's go for the rectangles!". But I was wrong ...
Rectangular Blues
The main problem with the rectangles is that querying the intersection is a nasty function. Something like:
So, when I tried to feed up Mathematica with a lot of these conditions for the equation, it performed so badly that I decided to do something procedural.
My algorithm ended up as follows:
Expand each rectangle size by a few points to get gaps in final configuration
While There are intersections
sort list of rectangles by number of intersections
push most intersected rectangle on stack, and remove it from list
// Now all remaining rectangles doesn't intersect each other
While stack not empty
pop rectangle from stack and re-insert it into list
find the geometric center G of the chart (each time!)
find the movement vector M (from G to rectangle center)
move the rectangle incrementally in the direction of M (both sides)
until no intersections
Shrink the rectangles to its original size
You may note that the "smallest movement" condition is not completely satisfied (only in one direction). But I found that moving the rectangles in any direction to satisfy it, sometimes ends up with a confusing map changing for the user.
As I am designing a user interface, I choose to move the rectangle a little further, but in a more predictable way. You can change the algorithm to inspect all angles and all radii surrounding its current position until an empty place is found, although it'll be much more demanding.
Anyway, these are examples of the results (before/ after):
Edit> More examples here
As you may see, the "minimum movement" is not satisfied, but the results are good enough.
I'll post the code here because I'm having some trouble with my SVN repository. I'll remove it when the problems are solved.
Edit:
You may also use R-Trees for finding rectangle intersections, but it seems an overkill for dealing with a small number of rectangles. And I haven't the algorithms already implemented. Perhaps someone else can point you to an existing implementation on your platform of choice.
Warning! Code is a first approach .. not great quality yet, and surely has some bugs.
It's Mathematica.
(*Define some functions first*)
Clear["Global`*"];
rn[x_] := RandomReal[{0, x}];
rnR[x_] := RandomReal[{1, x}];
rndCol[] := RGBColor[rn[1], rn[1], rn[1]];
minX[l_, i_] := l[[i]][[1]][[1]]; (*just for easy reading*)
maxX[l_, i_] := l[[i]][[1]][[2]];
minY[l_, i_] := l[[i]][[2]][[1]];
maxY[l_, i_] := l[[i]][[2]][[2]];
color[l_, i_]:= l[[i]][[3]];
intersectsQ[l_, i_, j_] := (* l list, (i,j) indexes,
list={{x1,x2},{y1,y2}} *)
(*A rect does intesect with itself*)
If[Max[minX[l, i], minX[l, j]] < Min[maxX[l, i], maxX[l, j]] &&
Max[minY[l, i], minY[l, j]] < Min[maxY[l, i], maxY[l, j]],
True,False];
(* Number of Intersects for a Rectangle *)
(* With i as index*)
countIntersects[l_, i_] :=
Count[Table[intersectsQ[l, i, j], {j, 1, Length[l]}], True]-1;
(*And With r as rectangle *)
countIntersectsR[l_, r_] := (
Return[Count[Table[intersectsQ[Append[l, r], Length[l] + 1, j],
{j, 1, Length[l] + 1}], True] - 2];)
(* Get the maximum intersections for all rectangles*)
findMaxIntesections[l_] := Max[Table[countIntersects[l, i],
{i, 1, Length[l]}]];
(* Get the rectangle center *)
rectCenter[l_, i_] := {1/2 (maxX[l, i] + minX[l, i] ),
1/2 (maxY[l, i] + minY[l, i] )};
(* Get the Geom center of the whole figure (list), to move aesthetically*)
geometryCenter[l_] := (* returs {x,y} *)
Mean[Table[rectCenter[l, i], {i, Length[l]}]];
(* Increment or decr. size of all rects by a bit (put/remove borders)*)
changeSize[l_, incr_] :=
Table[{{minX[l, i] - incr, maxX[l, i] + incr},
{minY[l, i] - incr, maxY[l, i] + incr},
color[l, i]},
{i, Length[l]}];
sortListByIntersections[l_] := (* Order list by most intersecting Rects*)
Module[{a, b},
a = MapIndexed[{countIntersectsR[l, #1], #2} &, l];
b = SortBy[a, -#[[1]] &];
Return[Table[l[[b[[i]][[2]][[1]]]], {i, Length[b]}]];
];
(* Utility Functions*)
deb[x_] := (Print["--------"]; Print[x]; Print["---------"];)(* for debug *)
tableForPlot[l_] := (*for plotting*)
Table[{color[l, i], Rectangle[{minX[l, i], minY[l, i]},
{maxX[l, i], maxY[l, i]}]}, {i, Length[l]}];
genList[nonOverlap_, Overlap_] := (* Generate initial lists of rects*)
Module[{alist, blist, a, b},
(alist = (* Generate non overlapping - Tabuloid *)
Table[{{Mod[i, 3], Mod[i, 3] + .8},
{Mod[i, 4], Mod[i, 4] + .8},
rndCol[]}, {i, nonOverlap}];
blist = (* Random overlapping *)
Table[{{a = rnR[3], a + rnR[2]}, {b = rnR[3], b + rnR[2]},
rndCol[]}, {Overlap}];
Return[Join[alist, blist] (* Join both *)];)
];
Main
clist = genList[6, 4]; (* Generate a mix fixed & random set *)
incr = 0.05; (* may be some heuristics needed to determine best increment*)
clist = changeSize[clist,incr]; (* expand rects so that borders does not
touch each other*)
(* Now remove all intercepting rectangles until no more intersections *)
workList = {}; (* the stack*)
While[findMaxIntesections[clist] > 0,
(*Iterate until no intersections *)
clist = sortListByIntersections[clist];
(*Put the most intersected first*)
PrependTo[workList, First[clist]];
(* Push workList with intersected *)
clist = Delete[clist, 1]; (* and Drop it from clist *)
];
(* There are no intersections now, lets pop the stack*)
While [workList != {},
PrependTo[clist, First[workList]];
(*Push first element in front of clist*)
workList = Delete[workList, 1];
(* and Drop it from worklist *)
toMoveIndex = 1;
(*Will move the most intersected Rect*)
g = geometryCenter[clist];
(*so the geom. perception is preserved*)
vectorToMove = rectCenter[clist, toMoveIndex] - g;
If [Norm[vectorToMove] < 0.01, vectorToMove = {1,1}]; (*just in case*)
vectorToMove = vectorToMove/Norm[vectorToMove];
(*to manage step size wisely*)
(*Now iterate finding minimum move first one way, then the other*)
i = 1; (*movement quantity*)
While[countIntersects[clist, toMoveIndex] != 0,
(*If the Rect still intersects*)
(*move it alternating ways (-1)^n *)
clist[[toMoveIndex]][[1]] += (-1)^i i incr vectorToMove[[1]];(*X coords*)
clist[[toMoveIndex]][[2]] += (-1)^i i incr vectorToMove[[2]];(*Y coords*)
i++;
];
];
clist = changeSize[clist, -incr](* restore original sizes*);
HTH!
Edit: Multi-angle searching
I implemented a change in the algorithm allowing to search in all directions, but giving preference to the axis imposed by the geometric symmetry.
At the expense of more cycles, this resulted in more compact final configurations, as you can see here below:
More samples here.
The pseudocode for the main loop changed to:
Expand each rectangle size by a few points to get gaps in final configuration
While There are intersections
sort list of rectangles by number of intersections
push most intersected rectangle on stack, and remove it from list
// Now all remaining rectangles doesn't intersect each other
While stack not empty
find the geometric center G of the chart (each time!)
find the PREFERRED movement vector M (from G to rectangle center)
pop rectangle from stack
With the rectangle
While there are intersections (list+rectangle)
For increasing movement modulus
For increasing angle (0, Pi/4)
rotate vector M expanding the angle alongside M
(* angle, -angle, Pi + angle, Pi-angle*)
re-position the rectangle accorging to M
Re-insert modified vector into list
Shrink the rectangles to its original size
I'm not including the source code for brevity, but just ask for it if you think you can use it. I think that, should you go this way, it's better to switch to R-trees (a lot of interval tests needed here)
这篇关于一个算法的空间了重叠的矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
