Ein Algorithmus zum Platzieren überlappender Rechtecke?

91

Dieses Problem betrifft tatsächlich Rollover. Ich werde es im Folgenden als solches verallgemeinern:

Ich habe eine 2D-Ansicht und eine Reihe von Rechtecken in einem Bereich auf dem Bildschirm. Wie verteile ich diese Felder so, dass sie sich nicht überlappen, sondern nur mit minimaler Bewegung anpassen?

Die Positionen der Rechtecke sind dynamisch und hängen von den Eingaben des Benutzers ab, sodass ihre Positionen überall sein können.

Angehängte Alt-TextBilder zeigen das Problem und die gewünschte Lösung

Das eigentliche Problem betrifft eigentlich Überschläge.

Antworten auf die Fragen in den Kommentaren

  1. Die Größe der Rechtecke ist nicht festgelegt und hängt von der Länge des Texts im Rollover ab

  2. In Bezug auf die Bildschirmgröße denke ich, dass es im Moment besser ist anzunehmen, dass die Größe des Bildschirms für die Rechtecke ausreicht. Wenn es zu viele Rechtecke gibt und der Algo keine Lösung liefert, muss ich nur den Inhalt optimieren.

  3. Die Anforderung, sich nur minimal zu bewegen, ist für die Asethetik mehr als eine absolute technische Anforderung. Man könnte zwei Rechtecke ausräumen, indem man einen großen Abstand zwischen ihnen hinzufügt, aber es sieht als Teil der GUI nicht gut aus. Die Idee ist, den Rollover / das Rechteck so nah wie möglich an seine Quelle zu bringen (die ich dann mit einer schwarzen Linie mit der Quelle verbinden werde). Es ist also in Ordnung, entweder nur eine für x oder beide für die Hälfte von x zu verschieben.

Extrakun
quelle
2
Können wir annehmen, dass die Rechtecke immer horizontal oder vertikal ausgerichtet und nicht in einem Winkel um ihre Achse geneigt sind?
Matt
2
Ja, die Annahme ist gültig.
Extrakun
Können wir davon ausgehen, dass der Bildschirm immer groß genug ist, um die Rechtecke ohne Überlappung zu unterstützen? Sind die Rechtecke immer gleich groß? Können Sie genauer sagen, was "minimale Bewegung" bedeutet? Wenn Sie beispielsweise zwei Rechtecke haben, die genau übereinander sitzen, ist es besser, nur eines davon über den gesamten Abstand zu entfernen, um die Überlappung zu beseitigen, oder beide Rechtecke um den halben Abstand zu verschieben?
Nick Larsen
@ NickLarsen, ich habe Ihre Fragen in der bearbeiteten Antwort oben beantwortet. Vielen Dank!
Extrakun
1
@joe: Vielleicht möchte er die Lösung verstehen, damit er sie unterstützen kann.
Beska

Antworten:

95

Ich habe ein bisschen daran gearbeitet, da ich auch etwas Ähnliches brauchte, aber ich hatte die Algorithmusentwicklung verzögert. Du hast mir geholfen, einen Impuls zu bekommen: D.

Ich brauchte auch den Quellcode, also hier ist er. Ich habe es in Mathematica ausgearbeitet, aber da ich die Funktionsmerkmale nicht stark genutzt habe, wird es wahrscheinlich einfach sein, in eine prozedurale Sprache zu übersetzen.

Eine historische Perspektive

Zuerst habe ich beschlossen, den Algorithmus für Kreise zu entwickeln, da der Schnittpunkt einfacher zu berechnen ist. Es kommt nur auf die Zentren und Radien an.

Ich konnte den Mathematica-Gleichungslöser verwenden, und er lief gut.

Schau einfach:

Alt-Text

Es war einfach. Ich habe gerade den Solver mit folgendem Problem geladen:

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
   ]

So einfach wie das, und Mathematica hat die ganze Arbeit gemacht.

Ich sagte "Ha! Es ist einfach, jetzt lass uns zu den Rechtecken gehen!". Aber ich habe mich getäuscht ...

Rechteckiger Blues

Das Hauptproblem bei den Rechtecken besteht darin, dass das Abfragen der Kreuzung eine unangenehme Funktion ist. Etwas wie:

Als ich versuchte, Mathematica mit vielen dieser Bedingungen für die Gleichung zu versorgen, lief es so schlecht, dass ich mich entschied, etwas prozedurales zu tun.

Mein Algorithmus endete wie folgt:

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

Möglicherweise stellen Sie fest, dass die Bedingung "kleinste Bewegung" nicht vollständig erfüllt ist (nur in eine Richtung). Aber ich fand heraus, dass das Bewegen der Rechtecke in eine beliebige Richtung, um sie zu befriedigen, manchmal zu einer verwirrenden Kartenänderung für den Benutzer führt.

Während ich eine Benutzeroberfläche entwerfe, verschiebe ich das Rechteck etwas weiter, aber vorhersehbarer. Sie können den Algorithmus ändern, um alle Winkel und alle Radien zu untersuchen, die seine aktuelle Position umgeben, bis eine leere Stelle gefunden wird, obwohl dies viel anspruchsvoller ist.

Auf jeden Fall sind dies Beispiele für die Ergebnisse (vorher / nachher):

Alt-Text

Bearbeiten> Weitere Beispiele hier

Wie Sie vielleicht sehen, ist die "minimale Bewegung" nicht zufriedenstellend, aber die Ergebnisse sind gut genug.

Ich werde den Code hier veröffentlichen, da ich Probleme mit meinem SVN-Repository habe. Ich werde es entfernen, wenn die Probleme gelöst sind.

Bearbeiten:

Sie können auch R-Bäume verwenden, um Rechteckkreuzungen zu finden, aber es scheint ein Overkill für den Umgang mit einer kleinen Anzahl von Rechtecken zu sein. Und ich habe die Algorithmen noch nicht implementiert. Vielleicht kann Sie jemand anderes auf eine vorhandene Implementierung auf der Plattform Ihrer Wahl verweisen.

Warnung! Code ist ein erster Ansatz. Noch keine gute Qualität und hat sicherlich einige Fehler.

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

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

HTH!

Bearbeiten: Mehrwinkelsuche

Ich habe eine Änderung im Algorithmus implementiert, die es ermöglicht, in alle Richtungen zu suchen, wobei jedoch die durch die geometrische Symmetrie auferlegte Achse bevorzugt wird.
Auf Kosten von mehr Zyklen führte dies zu kompakteren endgültigen Konfigurationen, wie Sie hier unten sehen können:

Geben Sie hier die Bildbeschreibung ein

Weitere Beispiele hier .

Der Pseudocode für die Hauptschleife wurde geändert 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

Der Kürze halber füge ich den Quellcode nicht hinzu, aber frage einfach danach, wenn du denkst, dass du ihn verwenden kannst. Ich denke, wenn Sie diesen Weg gehen, ist es besser, zu R-Bäumen zu wechseln (hier sind viele Intervalltests erforderlich).

Belisarius
quelle
4
Schön. Mein Freund und ich versuchen es umzusetzen. Daumen drücken Danke für die Zeit, dies aufzustellen!
Extrakun
9
Erklären des Denkprozesses, des Algorithmuskonzepts, der Schwierigkeiten und Einschränkungen und Bereitstellen von Code == +1. Und mehr, wenn ich es anbieten könnte.
Beska
1
@belisarlus Großartig schreiben! Haben Sie jemals Ihre Quelle veröffentlicht?
Rohan West
Hier gibt es andere Antworten, die versuchen, dies auf Java-Weise zu beantworten. Hat jemand diese mathematica-Lösung erfolgreich auf Java portiert?
Mainstringargs
11

Hier ist eine Vermutung.

Suchen Sie die Mitte C des Begrenzungsrahmens Ihrer Rechtecke.

Für jedes Rechteck R, das ein anderes überlappt.

  1. Definieren Sie einen Bewegungsvektor v.
  2. Finden Sie alle Rechtecke R ', die R überlappen.
  3. Addiere einen Vektor zu v proportional zum Vektor zwischen der Mitte von R und R '.
  4. Addiere einen Vektor zu v proportional zum Vektor zwischen C und dem Zentrum von R.
  5. Bewegen Sie R um v.
  6. Wiederholen, bis sich nichts überlappt.

Dadurch werden die Rechtecke schrittweise voneinander und von der Mitte aller Rechtecke weg verschoben. Dies wird beendet, weil die Komponente von v aus Schritt 4 sie schließlich von selbst genug verteilt.

cape1232
quelle
Gute Idee, die Mitte zu finden und die Rechtecke darüber zu verschieben. +1 Das einzige Problem ist, dass das Finden des Zentrums ein weiteres Problem für sich ist, das für jedes hinzugefügte Rechteck wahrscheinlich viel schwieriger ist.
Nick Larsen
2
Das Zentrum zu finden ist einfach. Nehmen Sie einfach das Min und Max der Ecken aller Rechtecke. Und Sie tun es nur einmal, nicht einmal pro Iteration.
Kap 1232
Dies führt auch zu einer minimalen Bewegung in dem Sinne, dass ein Rechteck nicht bewegt wird, wenn nichts es überlappt. Oh, Schritt 4 tut es, also sollten Sie Schritt 4 überspringen, wenn es keine Überlappungen gibt. Es ist wahrscheinlich viel schwieriger, die tatsächliche Anordnung zu finden, die nur minimale Bewegung erfordert.
Cape1232
Bei zwei Rechtecken in einer Ecke des sichtbaren Bereichs sollte die Alge verstehen können, ob das Diagramm erweitert oder verkleinert werden soll. Nur schimpfen. (Ich weiß, dass die Sichtbarkeit noch nicht im Geltungsbereich liegt, aber ich denke, es ist wichtig, das Problem nicht durch einfaches Erweitern des Diagramms zu lösen, denn wenn nicht, ist die Lösung trivial: Nehmen Sie die beiden nächsten Quadrate und "bestrahlen" Sie das gesamte Diagramm von seinem Schwerpunkt genug, um diese beiden Rechtecke auseinander zu bekommen). Ihr Ansatz ist natürlich besser. Ich sage nur, dass wir nicht expandieren sollten, wenn es nicht notwendig ist.
Dr. Belisarius
@belisarius Dies wird nicht erweitert, wenn es nicht notwendig ist. Sobald nichts Ihr Rechteck überlappt, bewegt es sich nicht mehr. (Es wird möglicherweise erneut gestartet, aber nur dann, wenn dies erforderlich ist.) Wenn genügend oder große Rechtecke vorhanden sind, können möglicherweise nicht alle Rechtecke in voller Größe auf dem Bildschirm angezeigt werden. In diesem Fall ist es einfach, den Begrenzungsrahmen der ersetzten Lösung zu finden und alles gleich zu skalieren, damit es auf den Bildschirm passt.
Cape1232
6

Ich denke, diese Lösung ist der von cape1232 ziemlich ähnlich, aber sie ist bereits implementiert, es lohnt sich also, sie sich anzusehen :)

Folgen Sie dieser reddit-Diskussion: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/ und lesen Sie die Beschreibung und Implementierung. Da kein Quellcode verfügbar ist, ist hier meine Herangehensweise an dieses Problem in AS3 (funktioniert genauso, behält jedoch die Rechtecke in der Auflösung des Rasters bei):

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;
            }
        }
    }
}
b005t3r
quelle
Es gibt einen Fehler in der Logik. Wie für einen Raum velocityist die Summe der Vektoren zwischen seiner Mitte und der Mitte der anderen Räume, wenn alle Räume mit der gleichen Mitte gestapelt sind, velocity.length == 0für alle Räume und nichts wird sich jemals bewegen. Wenn zwei oder mehr Räume dasselbe Rechteck mit derselben Mitte haben, bewegen sie sich auf die gleiche Weise zusammen, bleiben jedoch gestapelt.
Peyre
6

Die Implementierung von b005t3r gefällt mir sehr gut! Es funktioniert in meinen Testfällen, aber mein Repräsentant ist zu niedrig, um einen Kommentar mit den 2 vorgeschlagenen Korrekturen zu hinterlassen.

  1. Sie sollten Räume nicht in Schritten mit einer Auflösung übersetzen, sondern mit der Geschwindigkeit, die Sie gerade berechnet haben! Dies macht die Trennung organischer, da tief geschnittene Räume bei jeder Iteration mehr voneinander trennen als nicht so tief schneidende Räume.

  2. Sie sollten nicht davon ausgehen, dass Velociites unter 0,5 bedeuten, dass Räume getrennt sind, da Sie in einem Fall stecken bleiben können, in dem Sie niemals getrennt sind. Stellen Sie sich vor, 2 Räume kreuzen sich, können sich jedoch nicht selbst korrigieren, da jedes Mal, wenn einer der beiden versucht, die Penetration zu korrigieren, die erforderliche Geschwindigkeit mit <0,5 berechnet wird, sodass sie endlos iterieren.

Hier ist eine Java-Lösung (: 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);
Cord Rehn
quelle
4

Hier ist ein Algorithmus, der mit Java für die Behandlung eines Clusters nicht gedrehter Rectangles geschrieben wurde. Sie können das gewünschte Seitenverhältnis des Layouts festlegen und den Cluster mithilfe eines Rectangleals Ankerpunkt parametrisierten Parameters positionieren , an dem sich alle vorgenommenen Übersetzungen orientieren. Sie können auch eine beliebige Menge an Polsterung angeben, um die Sie das Rectangles verteilen möchten.

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

}}

Hier ist ein Beispiel mit einem AspectRatiovon 1.2, einem FillPercentagevon 0.8und einem Paddingvon 10.0.

100 zufällig skalierte und verteilte Rechtecke.

Die 100 zufälligen Rechtecke, die mit BoxxyDistribution verteilt wurden.

Dies ist ein deterministischer Ansatz, bei dem Abstände um den Anker herum auftreten können, während die Position des Ankers selbst unverändert bleibt. Auf diese Weise kann das Layout überall dort ausgeführt werden, wo sich der Point of Interest des Benutzers befindet. Die Logik zum Auswählen einer Position ist ziemlich simpel, aber ich denke, die umgebende Architektur, die Elemente nach ihrer Anfangsposition zu sortieren und sie dann zu iterieren, ist ein nützlicher Ansatz zur Implementierung einer relativ vorhersehbaren Verteilung. Außerdem verlassen wir uns nicht auf iterative Schnittpunkttests oder ähnliches, sondern bauen nur einige Begrenzungsrahmen auf, um einen umfassenden Hinweis darauf zu erhalten, wo die Dinge ausgerichtet werden müssen. Danach ist das Auftragen von Polstern ganz natürlich.

Mapsy
quelle
3

Hier ist eine Version, die die Antwort von cape1232 übernimmt und ein eigenständiges ausführbares Beispiel für Java ist:

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();

            }
        });
    }

}
Hauptstränge
quelle