Search code examples
algorithmuser-interfacelanguage-agnosticgraphics

An algorithm to space out overlapping rectangles?

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.

Attachedalt text images show the problem and desired solution

The real life problem deals with rollovers, actually.

Answers to the questions in the comments

  1. Size of rectangles is not fixed, and is dependent on the length of the text in the rollover

  2. 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.

  3. 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.

Solution

  • 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:

    alt text

    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):

    alt text

    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:

    enter image description here

    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)