Я немного работал над этим, так как мне нужно было что-то похожее, но я задержал разработку алгоритма. Вы помогли мне получить импульс: 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
Вы можете заметить, что условие «наименьшее движение» не полностью выполнено (только в одном направлении). Но я обнаружил, что перемещение прямоугольников в любом направлении, чтобы удовлетворить его, иногда заканчивается изменчивой картой, изменяющейся для пользователя.
Поскольку я проектирую пользовательский интерфейс, я решил переместить прямоугольник немного дальше, но более предсказуемым образом. Вы можете изменить алгоритм для проверки всех углов и всех радиусов, окружающих его текущее положение, пока не будет найдено пустое место, хотя это будет гораздо более требовательным.
В любом случае, это примеры результатов (до / после):
Редактировать> Дополнительные примеры здесь
Как видите, «минимальное движение» не выполняется, но результаты достаточно хороши.
Я опубликую код здесь, потому что у меня возникли проблемы с моим репозиторием 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 *)];)
];
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*);
НТН!
Редактировать: поиск под несколькими углами
Я реализовал изменение в алгоритме, позволяющем искать во всех направлениях, но отдавая предпочтение оси, наложенной геометрической симметрией.
За счет большего количества циклов это привело к более компактным окончательным конфигурациям, как вы можете видеть здесь ниже:
Больше образцов здесь .
Псевдокод для основного цикла изменен на:
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-деревья (здесь нужно много интервальных тестов)