Trochę nad tym pracowałem, bo też potrzebowałem czegoś podobnego, ale opóźniłem rozwój algorytmu. Pomogłeś mi nabrać impulsu: D
Potrzebowałem też kodu źródłowego, więc oto on. Opracowałem to w Mathematica, ale ponieważ nie korzystałem zbytnio z funkcji funkcjonalnych, myślę, że będzie łatwo przetłumaczyć na dowolny język proceduralny.
Perspektywa historyczna
Najpierw postanowiłem opracować algorytm dla okręgów, ponieważ przecięcie jest łatwiejsze do obliczenia. Zależy to tylko od środków i promieni.
Udało mi się skorzystać z narzędzia do rozwiązywania równań Mathematica i działało dobrze.
Spójrz:
To było proste. Właśnie załadowałem solvera z następującym problemem:
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
]
Tak proste, a Mathematica wykonała całą pracę.
Powiedziałem: „Ha! To proste, teraz przejdźmy do prostokątów!”. Ale byłem w błędzie ...
Prostokątne bluesy
Główny problem z prostokątami polega na tym, że zapytanie o przecięcie jest nieprzyjemną funkcją. Coś jak:
Tak więc, kiedy próbowałem zasilić Mathematica wieloma z tych warunków do równania, działało tak źle, że zdecydowałem się zrobić coś proceduralnego.
Mój algorytm zakończył się następująco:
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
Możesz zauważyć, że warunek „najmniejszego ruchu” nie jest w pełni spełniony (tylko w jednym kierunku). Ale odkryłem, że przesuwanie prostokątów w dowolnym kierunku, aby to zaspokoić, czasami kończy się mylącą zmianą mapy dla użytkownika.
Projektując interfejs użytkownika, wybieram przesunięcie prostokąta nieco dalej, ale w bardziej przewidywalny sposób. Możesz zmienić algorytm, aby sprawdzić wszystkie kąty i wszystkie promienie otaczające jego bieżącą pozycję, aż zostanie znalezione puste miejsce, chociaż będzie to znacznie bardziej wymagające.
W każdym razie są to przykłady wyników (przed / po):
Edytuj> Więcej przykładów tutaj
Jak widać, „minimalny ruch” nie jest spełniony, ale wyniki są wystarczająco dobre.
Opublikuję kod tutaj, ponieważ mam problemy z repozytorium SVN. Usunę go, gdy problemy zostaną rozwiązane.
Edytować:
Możesz również użyć R-drzew do znajdowania przecięć prostokątów, ale wydaje się to przesadą do radzenia sobie z niewielką liczbą prostokątów. I nie mam już zaimplementowanych algorytmów. Być może ktoś inny wskaże Ci istniejącą implementację na wybranej platformie.
Ostrzeżenie! Kod to pierwsze podejście… nie jest to jeszcze świetna jakość i na pewno ma kilka błędów.
To 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 *)];)
];
Główny
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!
Edycja: wyszukiwanie pod wieloma kątami
Zaimplementowałem zmianę w algorytmie pozwalającą na wyszukiwanie we wszystkich kierunkach, ale dającą pierwszeństwo osi narzuconej przez symetrię geometryczną.
Kosztem większej liczby cykli skutkowało to bardziej zwartymi konfiguracjami końcowymi, jak widać poniżej:
Więcej próbek tutaj .
Pseudokod głównej pętli został zmieniony na:
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
Nie dołączam kodu źródłowego dla zwięzłości, ale po prostu poproś o to, jeśli uważasz, że możesz go użyć. Myślę, że jeśli pójdziesz tą drogą, lepiej przełączyć się na R-drzewka (potrzeba tutaj dużo testów interwałowych)
obrazy przedstawiają problem i pożądane rozwiązanie
