Алгоритм для растягивания перекрывающихся прямоугольников?

Я немного работал над этим, так как мне тоже нужно было что-то подобное, но я задержал разработку алгоритма. Вы помогли мне получить импульс: 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 сделала всю работу.

Я сказал: «Ха! Легко, теперь займемся прямоугольниками!». Но я был неправ ...

Rectangular Blues

Основная проблема с прямоугольниками в том, что запрос пересечения - неприятная функция. Что-то вроде:

Итак, когда я попытался подкормить 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

Вы можете заметить, что условие «наименьшего движения» не выполняется полностью (только в одном направлении). Но я обнаружил, что перемещение прямоугольников в любом направлении для его удовлетворения иногда приводит к запутанному изменению карты для пользователя.

При разработке пользовательского интерфейса я решаю сдвинуть прямоугольник немного дальше, но более предсказуемым образом.Вы можете изменить алгоритм, чтобы проверять все углы и все радиусы вокруг его текущего положения, пока не будет найдено пустое место, хотя это будет намного сложнее.

В любом случае, это примеры результатов (до / после):

Правка> Дополнительные примеры здесь

Как видите, «минимальное перемещение» не выполняется, но результаты хорошие достаточно.

Я отправлю код сюда, потому что у меня проблемы с моим репозиторием SVN. Уберу, когда решат проблемы.

Редактировать:

Вы также можете использовать R-Trees для поиска пересечений прямоугольников, но это кажется излишним для работы с небольшим количеством прямоугольников. И у меня еще нет реализованных алгоритмов. Возможно, кто-то еще может указать вам на существующую реализацию на выбранной вами платформе.

Предупреждение! Код - это первый подход ... еще не очень высокого качества, и, конечно же, в нем есть некоторые ошибки.

Это 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 *)];)
      ];

Главная

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!

Редактировать: многоугловой поиск

Я внес изменение в алгоритм, позволяющее искать во всех направлениях, но отдавая предпочтение оси, обусловленной геометрической симметрией.
За счет большего количества циклов это привело к более компактным окончательным конфигурациям, как вы можете видеть здесь ниже:

Больше примеров здесь .

Псевдокод для основного цикла изменен на:

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-деревья (здесь нужно много интервальных тестов)