Un algoritmo per distanziare i rettangoli sovrapposti?

Questo problema riguarda in realtà i rollover, mi limiterò a generalizzare in quanto tale:

Ho una vista 2D e ho un numero di rettangoli all’interno di un’area sullo schermo. Come faccio a diffondere quelle scatole in modo tale che non si sovrappongano l’una all’altra, ma solo regolarle con uno spostamento minimo?

Le posizioni dei rettangoli sono dinamiche e dipendono dall’input dell’utente, quindi le loro posizioni potrebbero essere ovunque.

Allegato alt text le immagini mostrano il problema e la soluzione desiderata

Il vero problema della vita riguarda i rollover, in realtà.

    Risposte alle domande nei commenti

    1. La dimensione dei rettangoli non è fissa e dipende dalla lunghezza del testo nel rollover

    2. A proposito delle dimensioni dello schermo, al momento penso sia meglio presumere che la dimensione dello schermo sia sufficiente per i rettangoli. Se ci sono troppi rettangoli e l’algo non produce soluzione, allora devo solo modificare il contenuto.

    3. L’esigenza di “spostare minimamente” è più per l’etica che per un requisito ingegneristico assoluto. Uno potrebbe distanziare due rettangoli aggiungendo una grande distanza tra loro, ma non sembrerà buono come parte della GUI. L’idea è di ottenere il rollover / il rettangolo il più vicino ansible alla sua sorgente (che poi collegherò alla sorgente con una linea nera). Quindi o ‘spostare solo uno per x’ o ‘spostare entrambi per metà x’ va bene.

    Stavo lavorando un po ‘in questo, poiché avevo anche bisogno di qualcosa di simile, ma avevo ritardato lo sviluppo dell’algoritmo. Mi hai aiutato a ottenere un impulso: D

    Avevo anche bisogno del codice sorgente, quindi eccolo qui. L’ho elaborato in Mathematica, ma poiché non ho usato molto le funzionalità, credo che sarà facile tradurre in qualsiasi linguaggio procedurale.

    Una prospettiva storica

    Per prima cosa ho deciso di sviluppare l’algoritmo per i cerchi, perché l’intersezione è più facile da calcolare. Dipende solo dai centri e dai raggi.

    Sono stato in grado di utilizzare il solutore di equazioni Mathematica, e ha funzionato bene.

    Guarda:

    alt text

    È stato facile. Ho appena caricato il risolutore con il seguente problema:

    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 ] 

    Semplice come quello, e Mathematica ha fatto tutto il lavoro.

    Ho detto “Ha! È facile, ora andiamo per i rettangoli!”. Ma mi sbagliavo …

    Blues rettangular

    Il problema principale con i rettangoli è che interrogare l’intersezione è una brutta funzione. Qualcosa di simile a:

    Quindi, quando ho cercato di alimentare Mathematica con molte di queste condizioni per l’equazione, si è comportato così male che ho deciso di fare qualcosa di procedurale.

    Il mio algoritmo è stato il seguente:

     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 

    È ansible notare che la condizione di “movimento più piccolo” non è completamente soddisfatta (solo in una direzione). Ma ho scoperto che spostare i rettangoli in qualsiasi direzione per soddisfarlo, a volte finisce con una mappa confusa che cambia per l’utente.

    Mentre sto progettando un’interfaccia utente, scelgo di spostare il rettangolo un po ‘più avanti, ma in un modo più prevedibile. È ansible modificare l’algoritmo per ispezionare tutti gli angoli e tutti i raggi che circondano la sua posizione corrente fino a trovare un posto vuoto, anche se sarà molto più impegnativo.

    Ad ogni modo, questi sono esempi dei risultati (prima / dopo):

    alt text

    Modifica> Altri esempi qui

    Come puoi vedere, il “movimento minimo” non è soddisfatto, ma i risultati sono abbastanza buoni.

    Inserirò il codice qui perché ho qualche problema con il mio repository SVN. Lo rimuoverò quando i problemi saranno risolti.

    Modificare:

    Puoi anche usare R-Trees per trovare intersezioni rettangolari, ma sembra eccessivo per trattare un piccolo numero di rettangoli. E non ho ancora implementato gli algoritmi. Forse qualcun altro può indicarti un’implementazione esistente sulla tua piattaforma preferita.

    Avvertimento! Il codice è un primo approccio, non di ottima qualità, e sicuramente ha alcuni bug.

    È 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 *)];) ]; 

    Principale

     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)^ii incr vectorToMove[[1]];(*X coords*) clist[[toMoveIndex]][[2]] += (-1)^ii incr vectorToMove[[2]];(*Y coords*) i++; ]; ]; clist = changeSize[clist, -incr](* restore original sizes*); 

    HTH!

    Modifica: ricerca su più angoli

    Ho implementato una modifica dell'algoritmo che consente di cercare in tutte le direzioni, ma dando la preferenza all'asse imposto dalla simmetria geometrica.
    A scapito di più cicli, questo ha portato a configurazioni finali più compatte, come potete vedere qui sotto:

    inserisci la descrizione dell'immagine qui

    Altri campioni qui .

    Lo pseudocodice del ciclo principale è cambiato in:

     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 

    Non sto includendo il codice sorgente per brevità, ma chiedilo se pensi di poterlo usare. Penso che, se dovessi andare in questo modo, è meglio passare agli alberi R (sono necessari molti test di intervallo)

    Ecco un’ipotesi.

    Trova il centro C del rettangolo di selezione dei tuoi rettangoli.

    Per ogni rettangolo R che si sovrappone a un altro.

    1. Definire un vettore di movimento v.
    2. Trova tutti i rettangoli R ‘che si sovrappongono a R.
    3. Aggiungi un vettore a v proporzionale al vettore tra il centro di R e R ‘.
    4. Aggiungi un vettore a v proporzionale al vettore tra C e il centro di R.
    5. Sposta R di v.
    6. Ripeti fino a quando non si sovrappone nulla.

    Questo sposta in modo incrementale i rettangoli l’uno dall’altro e il centro di tutti i rettangoli. Questo finirà perché il componente di v dal passo 4 alla fine li distribuirà abbastanza da solo.

    Penso che questa soluzione sia abbastanza simile a quella data da cape1232, ma è già implementata, quindi vale la pena controllare 🙂

    Segui questa discussione reddit: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/ e controlla la descrizione e l’implementazione. Non c’è un codice sorgente disponibile, quindi ecco il mio approccio a questo problema in AS3 (funziona esattamente allo stesso modo, ma mantiene i rettangoli spezzati alla risoluzione della griglia):

     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; } } } } 

    Mi piace molto l’implementazione di b005t3r! Funziona nei miei casi di test, tuttavia il mio rappresentante è troppo basso per lasciare un commento con le 2 correzioni suggerite.

    1. Non dovresti tradurre stanze con incrementi a risoluzione singola, dovresti tradurre con la velocità che hai appena calcolato stazionariamente! Ciò rende la separazione più organica in quanto le sale profondamente intersecate separano più ogni iterazione rispetto alle stanze che non si intersecano così profondamente.

    2. Non dovresti pensare che i minuti meno di 0.5 significino che le stanze sono separate, in quanto puoi rimanere bloccato in un caso in cui non sei mai separato. Immaginate che 2 stanze si intersecano, ma non sono in grado di correggersi perché ogni volta che uno tenta di correggere la penetrazione, calcola la velocità richiesta come <0,5 in modo da iterare all'infinito.

    Ecco una soluzione 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); 

    Ecco un algoritmo scritto usando Java per gestire un cluster di Rectangle non Rectangle . Consente di specificare il rapporto aspetto desiderato del layout e posizionare il cluster utilizzando un Rectangle parametrizzato come punto di ancoraggio, su cui sono orientate tutte le traduzioni effettuate. Puoi anche specificare una quantità arbitraria di padding su cui vorresti distribuire il Rectangle per.

     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 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 lRectangles = new ArrayList(pRectangles); /* Allocate a List to track the bounds of each Row. */ final List lRowBounds = new ArrayList(); // (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(){ @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()); } } } 

    }

    Ecco un esempio utilizzando AspectRatio di 1.2 , un FillPercentage di 0.8 e un Padding di 10.0 .

    100 rettangoli scalati e distribuiti in modo casuale.

    I 100 rettangoli casuali distribuiti utilizzando BoxxyDistribution.

    Questo è un approccio deterministico che consente la spaziatura attorno all'ancora lasciando inalterata la posizione dell'ancora stessa. Ciò consente al layout di verificarsi ovunque sia il punto di interesse dell'utente. La logica per selezionare una posizione è piuttosto semplicistica, ma penso che l'architettura circostante di ordinare gli elementi in base alla loro posizione iniziale e quindi iterarli sia un utile approccio per implementare una distribuzione relativamente prevedibile. Inoltre non stiamo facendo affidamento su test di intersezione iterativi o qualcosa del genere, semplicemente costruendo alcune caselle di delimitazione per darci un'ampia indicazione su dove allineare le cose; dopo questo, applicando l'imbottitura, viene naturale.

    Ecco una versione che accetta la risposta di cape1232 ed è un esempio eseguibile standalone per Java:

     public class Rectangles extends JPanel { List rectangles = new ArrayList(); { // 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 rectanglesToDraw; protected void reset() { rectanglesToDraw = rectangles; this.repaint(); } private List findIntersections(Rectangle2D rect, List rectList) { ArrayList intersections = new ArrayList(); for (Rectangle2D intersectingRect : rectList) { if (!rect.equals(intersectingRect) && intersectingRect.intersects(rect)) { intersections.add(intersectingRect); } } return intersections; } protected void fix() { rectanglesToDraw = new ArrayList(); 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 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 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 actionPerformsd(ActionEvent e) { rects.fix(); } }); JButton resetButton = new JButton("Reset"); resetButton.addActionListener(new ActionListener() { @Override public void actionPerformsd(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(); } }); } }