一种分隔重叠矩形的算法? [英] An algorithm to space out overlapping rectangles?
问题描述
这个问题实际上涉及翻转，我将在下面概括如下:
我有一个 2D 视图，并且在屏幕上的一个区域内有许多矩形.我如何展开这些框，使它们不会相互重叠，而只能以最小的移动来调整它们?
矩形的位置是动态的，取决于用户的输入，所以它们的位置可以在任何地方.
附加 图像显示问题和所需的解决方案
现实生活中的问题实际上是翻车.
回答评论中的问题
矩形的大小不固定，取决于翻转中文本的长度
关于屏幕尺寸，现在我认为最好假设屏幕尺寸足以容纳矩形.如果矩形太多并且算法无法产生解决方案，那么我只需要调整内容即可.
最小移动"的要求更多是出于美学而非绝对的工程要求.可以通过在两个矩形之间增加一个很大的距离来隔开两个矩形，但作为 GUI 的一部分，它看起来不太好.这个想法是让翻转/矩形尽可能靠近其源(然后我将用黑线连接到源).因此，无论是为 x 只移动一个"还是为 x 的一半移动两个"都可以.
我在这方面做了一些工作，因为我也需要类似的东西，但我推迟了算法的开发.你帮助我获得了一些冲动:D
我还需要源代码，所以在这里.我在 Mathematica 中解决了它，但由于我没有大量使用函数特性，我想它会很容易翻译成任何程序语言.
历史视角
首先我决定开发圆的算法，因为交集更容易计算.它只取决于中心和半径.
我能够使用 Mathematica 方程求解器，它的表现很好.
看看:
这很容易.我刚刚用以下问题加载了求解器:
对于每个圆圈解决[为圆寻找新坐标最小化到图像几何中心的距离考虑到中心之间的距离 >R1+R2 *对于所有其他圈子在圆心和圆心之间沿直线移动圆图形的几何中心]就这么简单，Mathematica 完成了所有工作.
我说哈！这很简单，现在让我们来看看矩形！".但我错了...
矩形蓝色
矩形的主要问题是查询交集是一个令人讨厌的功能.类似的东西:
所以，当我试图用很多这些条件来满足 Mathematica 的方程时，它的表现非常糟糕，我决定做一些程序化的事情.
我的算法最终如下:
将每个矩形大小扩大几个点以获得最终配置中的间隙虽然有交集按交叉点数对矩形列表进行排序将最相交的矩形推入堆栈，并将其从列表中删除//现在所有剩余的矩形不相交虽然堆栈不为空从堆栈中弹出矩形并将其重新插入列表找到图表的几何中心 G(每次！)找到运动向量 M(从 G 到矩形中心)沿 M 方向(两侧)递增移动矩形直到没有交叉点将矩形缩小到其原始大小您可能会注意到最小移动"条件并未完全满足(仅在一个方向上).但是我发现向任何方向移动矩形以满足它，有时最终会为用户带来令人困惑的地图变化.
在设计用户界面时，我选择将矩形移动得更远一些，但以更可预测的方式移动.您可以更改算法以检查其当前位置周围的所有角度和所有半径，直到找到一个空的地方，尽管它的要求会更高.
无论如何，这些是结果示例(之前/之后):
编辑>更多示例
更多示例此处.
主循环的伪代码改为:
将每个矩形大小扩大几个点以获得最终配置中的间隙虽然有交集按交叉点数对矩形列表进行排序将最相交的矩形推入堆栈，并将其从列表中删除//现在所有剩余的矩形不相交虽然堆栈不为空找到图表的几何中心 G(每次！)找到首选运动向量 M(从 G 到矩形中心)从堆栈中弹出矩形随着矩形虽然有交集(列表+矩形)用于增加运动模量增加角度 (0, Pi/4)旋转向量 M 沿 M 扩展角度(* 角, -角, Pi + 角, Pi 角*)根据 M 重新定位矩形将修改后的向量重新插入列表将矩形缩小到其原始大小为简洁起见，我不包括源代码，但如果您认为可以使用它，请索取.我认为，如果你走这条路，最好切换到R-trees(这里需要大量的间隔测试)
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屋！
