algorithm - 间隔重叠矩形的算法？

Question

这个问题实际上涉及翻转，我将在下面概括如下:

我有一个 2D View ，屏幕上的一个区域内有许多矩形。我如何展开这些盒子，使它们彼此不重叠，而仅以最小的移动来调整它们？

矩形的位置是动态的，取决于用户的输入，因此它们的位置可以在任何地方。

附图片显示问题和所需的解决方案

现实生活中的问题实际上与翻车有关。

评论中问题的答案

1. 矩形的大小不固定，取决于翻转中文本的长度

2. 关于屏幕尺寸，目前我认为最好假设屏幕尺寸足以容纳矩形。如果矩形太多并且算法无法生成解决方案，那么我只需要调整内容即可。

3. “最低限度移动”的要求更多的是美学而非绝对的工程要求。可以通过在两个矩形之间增加很大的距离来隔开两个矩形，但作为 GUI 的一部分看起来不太好。这个想法是让翻转/矩形尽可能靠近它的源(然后我将用黑线连接到源)。因此，“只为 x 移动一个”或“为一半 x 移动两个”都可以。

Answer 1

我在这方面做了一些工作，因为我也需要类似的东西，但我推迟了算法开发。你帮助我获得了一些冲动 :D

我还需要源代码，所以就在这里。我在 Mathematica 中解决了这个问题，但由于我没有大量使用函数特性，我想它很容易翻译成任何过程语言。

历史视角

首先我决定为圆开发算法，因为交点更容易计算。它仅取决于中心和半径。

我能够使用 Mathematica 方程求解器，它的性能非常好。

看看:

这很容易。我刚刚加载了具有以下问题的求解器:

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
   ]

就这么简单，Mathematica 完成了所有工作。

我说“哈!这很简单，现在让我们开始使用矩形吧!”。但是我错了...

矩形蓝调

矩形的主要问题是查询交集是一个讨厌的函数。像这样的东西:

因此，当我尝试为 Mathematica 提供方程式的这些条件时，它的表现非常糟糕，以至于我决定做一些程序化的事情。

我的算法最终如下:

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

您可能会注意到“最小移动”条件并未完全满足(仅在一个方向上)。但我发现向任何方向移动矩形以满足它，有时最终会导致用户混淆 map 更改。

在设计用户界面时，我选择将矩形移动得更远一些，但以一种更可预测的方式。您可以更改算法以检查其当前位置周围的所有角度和所有半径，直到找到一个空位，尽管这会要求更高。

无论如何，这些是结果的示例(之前/之后):

编辑> 更多例子here

如你所见，“最小移动”并不满足，但结果已经足够好了。

我将在此处发布代码，因为我在使用 SVN 存储库时遇到了一些问题。问题解决后我会删除它。

编辑:

您也可以使用 R-Trees用于查找矩形交点，但处理少量矩形似乎有点矫枉过正。而且我还没有实现算法。也许其他人可以向您指出您选择的平台上的现有实现。

警告!代码是第一种方法.. 质量还不是很好，肯定有一些错误。

这是数学。

(*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 *)];)
      ];

主要

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*);

喂!

编辑:多角度搜索

我对算法进行了更改，允许在所有方向上进行搜索，但优先考虑几何对称性强加的轴。
以更多的周期为代价，这导致了更紧凑的最终配置，如下所示:

更多 sample here .

主循环的伪代码改为:

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

为简洁起见，我没有包含源代码，但如果您认为可以使用它，请提出要求。我认为，如果你走这条路，最好切换到 R 树(这里需要很多间隔测试)