Algorytm rozdzielania nakładających się prostokątów?

Ten problem dotyczy w rzeczywistości przewrotów, po prostu uogólniam poniżej jako takie:

Mam widok 2D i kilka prostokątów w obszarze na ekranie. Jak rozłożyć te pola tak, aby nie zachodziły na siebie, a jedynie dopasować je przy minimalnym ruchu?

Pozycje prostokątów są dynamiczne i zależne od danych wejściowych użytkownika, więc ich pozycje mogą znajdować się w dowolnym miejscu.

Załączone obrazy przedstawiają problem i pożądane rozwiązanie

W rzeczywistości prawdziwy problem dotyczy kumulacji.

Odpowiedzi na pytania w komentarzach

1. Rozmiar prostokątów nie jest stały i zależy od długości tekstu w najeździe

2. Jeśli chodzi o rozmiar ekranu, teraz myślę, że lepiej założyć, że rozmiar ekranu jest wystarczający dla prostokątów. Jeśli jest zbyt wiele prostokątów, a algo nie daje rozwiązania, po prostu muszę dostosować zawartość.

3. Wymóg „minimalnego poruszania się” dotyczy raczej estetyki niż bezwzględnego wymogu inżynieryjnego. Można by oddzielić dwa prostokąty, dodając dużą odległość między nimi, ale nie będzie to dobrze wyglądać jako część GUI. Chodzi o to, aby najazd / prostokąt był tak blisko jego źródła (które następnie połączę ze źródłem za pomocą czarnej linii). Więc albo „przesuwanie tylko jednego o x” albo „przesuwanie obu o pół x” jest w porządku.

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)

Oto przypuszczenie.

Znajdź środek C obwiedni twoich prostokątów.

Dla każdego prostokąta R, który zachodzi na inny.

1. Zdefiniuj wektor ruchu v.
2. Znajdź wszystkie prostokąty R ', które nakładają się na R.
3. Dodaj wektor do v proporcjonalny do wektora między środkiem R i R '.
4. Dodaj wektor do v proporcjonalny do wektora między C i środkiem R.
5. Przesuń R o v.
6. Powtarzaj, aż nic się nie pokrywa.

To stopniowo przesuwa prostokąty od siebie i od środka wszystkich prostokątów. To zakończy się, ponieważ składnik v z kroku 4 w końcu sam je wystarczająco rozłoży.

Myślę, że to rozwiązanie jest dość podobne do tego, które daje cape1232, ale jest już zaimplementowane, więc warto sprawdzić :)

Śledź tę dyskusję na reddicie: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/ i sprawdź opis i implementację. Nie ma dostępnego kodu źródłowego, więc oto moje podejście do tego problemu w AS3 (działa dokładnie tak samo, ale utrzymuje prostokąty przyciągane do rozdzielczości siatki):

public class RoomSeparator extends AbstractAction {
    public function RoomSeparator(name:String = "Room Separator") {
        super(name);
    }

    override public function get finished():Boolean { return _step == 1; }

    override public function step():void {
        const repelDecayCoefficient:Number = 1.0;

        _step = 1;

        var count:int = _activeRoomContainer.children.length;
        for(var i:int = 0; i < count; i++) {
            var room:Room           = _activeRoomContainer.children[i];
            var center:Vector3D     = new Vector3D(room.x + room.width / 2, room.y + room.height / 2);
            var velocity:Vector3D   = new Vector3D();

            for(var j:int = 0; j < count; j++) {
                if(i == j)
                    continue;

                var otherRoom:Room = _activeRoomContainer.children[j];
                var intersection:Rectangle = GeomUtil.rectangleIntersection(room.createRectangle(), otherRoom.createRectangle());

                if(intersection == null || intersection.width == 0 || intersection.height == 0)
                    continue;

                var otherCenter:Vector3D = new Vector3D(otherRoom.x + otherRoom.width / 2, otherRoom.y + otherRoom.height / 2);
                var diff:Vector3D = center.subtract(otherCenter);

                if(diff.length > 0) {
                    var scale:Number = repelDecayCoefficient / diff.lengthSquared;
                    diff.normalize();
                    diff.scaleBy(scale);

                    velocity = velocity.add(diff);
                }
            }

            if(velocity.length > 0) {
                _step = 0;
                velocity.normalize();

                room.x += Math.abs(velocity.x) < 0.5 ? 0 : velocity.x > 0 ? _resolution : -_resolution;
                room.y += Math.abs(velocity.y) < 0.5 ? 0 : velocity.y > 0 ? _resolution : -_resolution;
            }
        }
    }
}

Bardzo podoba mi się implementacja b005t3r! Działa w moich przypadkach testowych, jednak mój przedstawiciel jest zbyt niski, aby zostawić komentarz z 2 sugerowanymi poprawkami.

1. Nie powinieneś tłumaczyć pokoi o pojedyncze przyrosty rozdzielczości, powinieneś tłumaczyć przez prędkość, którą po prostu precyzyjnie obliczyłeś! To sprawia, że ​​separacja jest bardziej organiczna, ponieważ głęboko przecinające się pokoje oddzielają się bardziej w każdej iteracji niż nie tak głęboko przecinające się pokoje.

2. Nie powinieneś zakładać, że velociity mniejsze niż 0,5 oznaczają oddzielne pokoje, ponieważ możesz utknąć w przypadku, gdy nigdy nie zostaniesz rozdzielony. Wyobraź sobie, że 2 pokoje się przecinają, ale nie są w stanie się poprawić, ponieważ za każdym razem, gdy którykolwiek z nich próbuje skorygować penetrację, obliczają wymaganą prędkość jako <0,5, więc iterują w nieskończoność.

Oto rozwiązanie Java (: Cheers!

do {
    _separated = true;

    for (Room room : getRooms()) {
        // reset for iteration
        Vector2 velocity = new Vector2();
        Vector2 center = room.createCenter();

        for (Room other_room : getRooms()) {
            if (room == other_room)
                continue;

            if (!room.createRectangle().overlaps(other_room.createRectangle()))
                continue;

            Vector2 other_center = other_room.createCenter();
            Vector2 diff = new Vector2(center.x - other_center.x, center.y - other_center.y);
            float diff_len2 = diff.len2();

            if (diff_len2 > 0f) {
                final float repelDecayCoefficient = 1.0f;
                float scale = repelDecayCoefficient / diff_len2;
                diff.nor();
                diff.scl(scale);

                velocity.add(diff);
            }
        }

        if (velocity.len2() > 0f) {
            _separated = false;

            velocity.nor().scl(delta * 20f);

            room.getPosition().add(velocity);
        }
    }
} while (!_separated);

Oto algorytm napisany przy użyciu języka Java do obsługi klastra nieobrotowych plików Rectangles. Pozwala określić pożądane proporcje układu i pozycjonuje klaster za pomocą sparametryzowanego Rectanglepunktu zakotwiczenia, na którym zorientowane są wszystkie wykonane tłumaczenia. Możesz również określić dowolną ilość wypełnienia, według której chcesz rozłożyć Rectangles.

public final class BoxxyDistribution {

/* Static Definitions. */
private static final int INDEX_BOUNDS_MINIMUM_X = 0;
private static final int INDEX_BOUNDS_MINIMUM_Y = 1;
private static final int INDEX_BOUNDS_MAXIMUM_X = 2;
private static final int INDEX_BOUNDS_MAXIMUM_Y = 3;

private static final double onCalculateMagnitude(final double pDeltaX, final double pDeltaY) {
    return Math.sqrt((pDeltaX * pDeltaX) + (pDeltaY + pDeltaY));
}

/* Updates the members of EnclosingBounds to ensure the dimensions of T can be completely encapsulated. */
private static final void onEncapsulateBounds(final double[] pEnclosingBounds, final double pMinimumX, final double pMinimumY, final double pMaximumX, final double pMaximumY) {
    pEnclosingBounds[0] = Math.min(pEnclosingBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X], pMinimumX);
    pEnclosingBounds[1] = Math.min(pEnclosingBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y], pMinimumY);
    pEnclosingBounds[2] = Math.max(pEnclosingBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X], pMaximumX);
    pEnclosingBounds[3] = Math.max(pEnclosingBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y], pMaximumY);
}

private static final void onEncapsulateBounds(final double[] pEnclosingBounds, final double[] pBounds) {
    BoxxyDistribution.onEncapsulateBounds(pEnclosingBounds, pBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X], pBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y], pBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X], pBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y]);
}

private static final double onCalculateMidpoint(final double pMaximum, final double pMinimum) {
    return ((pMaximum - pMinimum) * 0.5) + pMinimum;
}

/* Re-arranges a List of Rectangles into something aesthetically pleasing. */
public static final void onBoxxyDistribution(final List<Rectangle> pRectangles, final Rectangle pAnchor, final double pPadding, final double pAspectRatio, final float pRowFillPercentage) {
    /* Create a safe clone of the Rectangles that we can modify as we please. */
    final List<Rectangle> lRectangles  = new ArrayList<Rectangle>(pRectangles);
    /* Allocate a List to track the bounds of each Row. */
    final List<double[]>  lRowBounds   = new ArrayList<double[]>(); // (MinX, MinY, MaxX, MaxY)
    /* Ensure Rectangles does not contain the Anchor. */
    lRectangles.remove(pAnchor);
    /* Order the Rectangles via their proximity to the Anchor. */
    Collections.sort(pRectangles, new Comparator<Rectangle>(){ @Override public final int compare(final Rectangle pT0, final Rectangle pT1) {
        /* Calculate the Distance for pT0. */
        final double lDistance0 = BoxxyDistribution.onCalculateMagnitude(pAnchor.getCenterX() - pT0.getCenterX(), pAnchor.getCenterY() - pT0.getCenterY());
        final double lDistance1 = BoxxyDistribution.onCalculateMagnitude(pAnchor.getCenterX() - pT1.getCenterX(), pAnchor.getCenterY() - pT1.getCenterY());
        /* Compare the magnitude in distance between the anchor and the Rectangles. */
        return Double.compare(lDistance0, lDistance1);
    } });
    /* Initialize the RowBounds using the Anchor. */ /** TODO: Probably better to call getBounds() here. **/
    lRowBounds.add(new double[]{ pAnchor.getX(), pAnchor.getY(), pAnchor.getX() + pAnchor.getWidth(), pAnchor.getY() + pAnchor.getHeight() });

    /* Allocate a variable for tracking the TotalBounds of all rows. */
    final double[] lTotalBounds = new double[]{ Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY };
    /* Now we iterate the Rectangles to place them optimally about the Anchor. */
    for(int i = 0; i < lRectangles.size(); i++) {
        /* Fetch the Rectangle. */
        final Rectangle lRectangle = lRectangles.get(i);
        /* Iterate through each Row. */
        for(final double[] lBounds : lRowBounds) {
            /* Update the TotalBounds. */
            BoxxyDistribution.onEncapsulateBounds(lTotalBounds, lBounds);
        }
        /* Allocate a variable to state whether the Rectangle has been allocated a suitable RowBounds. */
        boolean lIsBounded = false;
        /* Calculate the AspectRatio. */
        final double lAspectRatio = (lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X] - lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X]) / (lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y] - lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y]);
        /* We will now iterate through each of the available Rows to determine if a Rectangle can be stored. */
        for(int j = 0; j < lRowBounds.size() && !lIsBounded; j++) {
            /* Fetch the Bounds. */
            final double[] lBounds = lRowBounds.get(j);
            /* Calculate the width and height of the Bounds. */
            final double   lWidth  = lBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X] - lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X];
            final double   lHeight = lBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y] - lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y];
            /* Determine whether the Rectangle is suitable to fit in the RowBounds. */
            if(lRectangle.getHeight() <= lHeight && !(lAspectRatio > pAspectRatio && lWidth > pRowFillPercentage * (lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X] - lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X]))) {
                /* Register that the Rectangle IsBounded. */
                lIsBounded = true;
                /* Update the Rectangle's X and Y Co-ordinates. */
                lRectangle.setFrame((lRectangle.getX() > BoxxyDistribution.onCalculateMidpoint(lBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X], lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X])) ? lBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X] + pPadding : lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X] - (pPadding + lRectangle.getWidth()), lBounds[1], lRectangle.getWidth(), lRectangle.getHeight());
                /* Update the Bounds. (Do not modify the vertical metrics.) */
                BoxxyDistribution.onEncapsulateBounds(lTotalBounds, lRectangle.getX(), lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y], lRectangle.getX() + lRectangle.getWidth(), lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y] + lHeight);
            }
        }
        /* Determine if the Rectangle has not been allocated a Row. */
        if(!lIsBounded) {
            /* Calculate the MidPoint of the TotalBounds. */
            final double lCentreY   = BoxxyDistribution.onCalculateMidpoint(lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y], lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y]);
            /* Determine whether to place the bounds above or below? */
            final double lYPosition = lRectangle.getY() < lCentreY ? lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y] - (pPadding + lRectangle.getHeight()) : (lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y] + pPadding);
            /* Create a new RowBounds. */
            final double[] lBounds  = new double[]{ pAnchor.getX(), lYPosition, pAnchor.getX() + lRectangle.getWidth(), lYPosition + lRectangle.getHeight() };
            /* Allocate a new row, roughly positioned about the anchor. */
            lRowBounds.add(lBounds);
            /* Position the Rectangle. */
            lRectangle.setFrame(lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X], lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y], lRectangle.getWidth(), lRectangle.getHeight());
        }
    }
}

}

Oto przykład użycia AspectRatioof 1.2, a FillPercentageof 0.8i a Paddingof 10.0.

Jest to podejście deterministyczne, które pozwala na występowanie odstępów wokół kotwy, pozostawiając niezmienione położenie samej kotwicy. Dzięki temu układ pojawia się wszędzie tam, gdzie znajduje się punkt zainteresowania użytkownika. Logika wyboru pozycji jest dość uproszczona, ale myślę, że otaczająca architektura sortowania elementów na podstawie ich początkowej pozycji, a następnie ich iteracja jest użytecznym podejściem do implementacji stosunkowo przewidywalnej dystrybucji. Poza tym nie polegamy na iteracyjnych testach przecięcia ani na czymś podobnym, po prostu budujemy kilka obwiedni, aby dać nam ogólne wskazówki, gdzie wyrównać rzeczy; potem nakładanie wyściółki przychodzi naturalnie.

Oto wersja, która przyjmuje odpowiedź cape1232 i jest samodzielnym uruchomionym przykładem dla Javy:

public class Rectangles extends JPanel {

    List<Rectangle2D> rectangles = new ArrayList<Rectangle2D>();
    {
        // x,y,w,h
        rectangles.add(new Rectangle2D.Float(300, 50, 50, 50));

        rectangles.add(new Rectangle2D.Float(300, 50, 20, 50));

        rectangles.add(new Rectangle2D.Float(100, 100, 100, 50));

        rectangles.add(new Rectangle2D.Float(120, 200, 50, 50));

        rectangles.add(new Rectangle2D.Float(150, 130, 100, 100));

        rectangles.add(new Rectangle2D.Float(0, 100, 100, 50));

        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                rectangles.add(new Rectangle2D.Float(i * 40, j * 40, 20, 20));
            }
        }
    }

    List<Rectangle2D> rectanglesToDraw;

    protected void reset() {
        rectanglesToDraw = rectangles;

        this.repaint();
    }

    private List<Rectangle2D> findIntersections(Rectangle2D rect, List<Rectangle2D> rectList) {

        ArrayList<Rectangle2D> intersections = new ArrayList<Rectangle2D>();

        for (Rectangle2D intersectingRect : rectList) {
            if (!rect.equals(intersectingRect) && intersectingRect.intersects(rect)) {
                intersections.add(intersectingRect);
            }
        }

        return intersections;
    }

    protected void fix() {
        rectanglesToDraw = new ArrayList<Rectangle2D>();

        for (Rectangle2D rect : rectangles) {
            Rectangle2D copyRect = new Rectangle2D.Double();
            copyRect.setRect(rect);
            rectanglesToDraw.add(copyRect);
        }

        // Find the center C of the bounding box of your rectangles.
        Rectangle2D surroundRect = surroundingRect(rectanglesToDraw);
        Point center = new Point((int) surroundRect.getCenterX(), (int) surroundRect.getCenterY());

        int movementFactor = 5;

        boolean hasIntersections = true;

        while (hasIntersections) {

            hasIntersections = false;

            for (Rectangle2D rect : rectanglesToDraw) {

                // Find all the rectangles R' that overlap R.
                List<Rectangle2D> intersectingRects = findIntersections(rect, rectanglesToDraw);

                if (intersectingRects.size() > 0) {

                    // Define a movement vector v.
                    Point movementVector = new Point(0, 0);

                    Point centerR = new Point((int) rect.getCenterX(), (int) rect.getCenterY());

                    // For each rectangle R that overlaps another.
                    for (Rectangle2D rPrime : intersectingRects) {
                        Point centerRPrime = new Point((int) rPrime.getCenterX(), (int) rPrime.getCenterY());

                        int xTrans = (int) (centerR.getX() - centerRPrime.getX());
                        int yTrans = (int) (centerR.getY() - centerRPrime.getY());

                        // Add a vector to v proportional to the vector between the center of R and R'.
                        movementVector.translate(xTrans < 0 ? -movementFactor : movementFactor,
                                yTrans < 0 ? -movementFactor : movementFactor);

                    }

                    int xTrans = (int) (centerR.getX() - center.getX());
                    int yTrans = (int) (centerR.getY() - center.getY());

                    // Add a vector to v proportional to the vector between C and the center of R.
                    movementVector.translate(xTrans < 0 ? -movementFactor : movementFactor,
                            yTrans < 0 ? -movementFactor : movementFactor);

                    // Move R by v.
                    rect.setRect(rect.getX() + movementVector.getX(), rect.getY() + movementVector.getY(),
                            rect.getWidth(), rect.getHeight());

                    // Repeat until nothing overlaps.
                    hasIntersections = true;
                }

            }
        }
        this.repaint();
    }

    private Rectangle2D surroundingRect(List<Rectangle2D> rectangles) {

        Point topLeft = null;
        Point bottomRight = null;

        for (Rectangle2D rect : rectangles) {
            if (topLeft == null) {
                topLeft = new Point((int) rect.getMinX(), (int) rect.getMinY());
            } else {
                if (rect.getMinX() < topLeft.getX()) {
                    topLeft.setLocation((int) rect.getMinX(), topLeft.getY());
                }

                if (rect.getMinY() < topLeft.getY()) {
                    topLeft.setLocation(topLeft.getX(), (int) rect.getMinY());
                }
            }

            if (bottomRight == null) {
                bottomRight = new Point((int) rect.getMaxX(), (int) rect.getMaxY());
            } else {
                if (rect.getMaxX() > bottomRight.getX()) {
                    bottomRight.setLocation((int) rect.getMaxX(), bottomRight.getY());
                }

                if (rect.getMaxY() > bottomRight.getY()) {
                    bottomRight.setLocation(bottomRight.getX(), (int) rect.getMaxY());
                }
            }
        }

        return new Rectangle2D.Double(topLeft.getX(), topLeft.getY(), bottomRight.getX() - topLeft.getX(),
                bottomRight.getY() - topLeft.getY());
    }

    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;

        for (Rectangle2D entry : rectanglesToDraw) {
            g2d.setStroke(new BasicStroke(1));
            // g2d.fillRect((int) entry.getX(), (int) entry.getY(), (int) entry.getWidth(),
            // (int) entry.getHeight());
            g2d.draw(entry);
        }

    }

    protected static void createAndShowGUI() {
        Rectangles rects = new Rectangles();

        rects.reset();

        JFrame frame = new JFrame("Rectangles");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setLayout(new BorderLayout());
        frame.add(rects, BorderLayout.CENTER);

        JPanel buttonsPanel = new JPanel();

        JButton fix = new JButton("Fix");

        fix.addActionListener(new ActionListener() {

            @Override
            public void actionPerformed(ActionEvent e) {
                rects.fix();

            }
        });

        JButton resetButton = new JButton("Reset");

        resetButton.addActionListener(new ActionListener() {

            @Override
            public void actionPerformed(ActionEvent e) {
                rects.reset();
            }
        });

        buttonsPanel.add(fix);
        buttonsPanel.add(resetButton);

        frame.add(buttonsPanel, BorderLayout.SOUTH);

        frame.setSize(400, 400);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {

            @Override
            public void run() {
                createAndShowGUI();

            }
        });
    }

}