Un algorithme pour espacer les rectangles qui se chevauchent ?

Question

Ce problème concerne en fait les roll-overs, je le généraliserai ci-dessous comme tel :

J'ai une vue 2D, et j'ai un certain nombre de rectangles dans une zone de l'écran. Comment puis-je répartir ces rectangles de manière à ce qu'ils ne se chevauchent pas, tout en les ajustant avec un minimum de mouvements ?

La position des rectangles est dynamique et dépend de l'entrée de l'utilisateur, de sorte que leur position peut être n'importe où.

Ci-joint les images montrent le problème et la solution souhaitée

Le problème réel concerne les renversements, en fait.

Réponses aux questions dans les commentaires

1. La taille des rectangles n'est pas fixe et dépend de la longueur du texte du rollover.

2. En ce qui concerne la taille de l'écran, pour l'instant, je pense qu'il est préférable de supposer que la taille de l'écran est suffisante pour les rectangles. S'il y a trop de rectangles et que l'algo ne produit aucune solution, il me suffit de modifier le contenu.

3. L'obligation de "bouger le moins possible" est plus une question d'esthétique qu'une exigence technique absolue. On pourrait espacer deux rectangles en ajoutant une grande distance entre eux, mais cela ne serait pas très esthétique dans l'interface graphique. L'idée est d'obtenir le rollover/rectangle aussi près que possible de sa source (que je relierai ensuite à la source avec une ligne noire). Donc, que ce soit en déplaçant un seul élément pour x ou en déplaçant les deux pour la moitié de x, cela convient.

Answer 1

J'ai travaillé un peu là-dessus, car j'avais aussi besoin de quelque chose de similaire, mais j'avais retardé le développement de l'algorithme. Vous m'avez aidé à prendre de l'élan :D

J'avais également besoin du code source, le voici donc. J'ai travaillé en Mathematica, mais comme je n'ai pas beaucoup utilisé les fonctionnalités, je pense qu'il sera facile de le traduire dans n'importe quel langage procédural.

Une perspective historique

J'ai d'abord décidé de développer l'algorithme pour les cercles, car l'intersection est plus facile à calculer. Cela dépend juste des centres et des rayons.

J'ai pu utiliser le solveur d'équations Mathematica, qui s'est bien comporté.

Regarde juste :

C'était facile. J'ai juste chargé le solveur avec le problème suivant :

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
   ]

C'est aussi simple que ça, et Mathematica a fait tout le travail.

J'ai dit "Ha ! c'est facile, maintenant allons-y pour les rectangles !". Mais j'avais tort...

Rectangulaire Blues

Le principal problème avec les rectangles est que l'interrogation de l'intersection est une fonction désagréable. Quelque chose comme :

Ainsi, lorsque j'ai essayé d'alimenter Mathematica avec un grand nombre de ces conditions pour l'équation, il s'est si mal comporté que j'ai décidé de faire quelque chose de procédural.

Mon algorithme a abouti à ce qui suit :

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

Vous pouvez noter que la condition du "plus petit mouvement" n'est pas complètement satisfaite (seulement dans une direction). Mais j'ai trouvé qu'en déplaçant les rectangles dans n'importe quelle direction pour la satisfaire, on aboutit parfois à un changement de carte déroutant pour l'utilisateur.

Comme je conçois une interface utilisateur, je choisis de déplacer le rectangle un peu plus loin, mais de manière plus prévisible. Vous pouvez modifier l'algorithme pour qu'il inspecte tous les angles et tous les rayons entourant sa position actuelle jusqu'à ce qu'il trouve une place vide, mais cela sera beaucoup plus exigeant.

Quoi qu'il en soit, voici des exemples de résultats (avant/après) :

Edit> Plus d'exemples aquí

Comme vous pouvez le constater, le "mouvement minimum" n'est pas satisfait, mais les résultats sont suffisamment bons.

Je vais poster le code ici car j'ai quelques problèmes avec mon dépôt SVN. Je le supprimerai lorsque les problèmes seront résolus.

Edit :

Vous pouvez également utiliser Arbres R pour trouver les intersections de rectangles, mais cela semble excessif pour traiter un petit nombre de rectangles. Et je n'ai pas les algorithmes déjà implémentés. Peut-être que quelqu'un d'autre peut vous indiquer une implémentation existante sur la plate-forme de votre choix.

Attention ! Le code est une première approche pas encore de grande qualité, et a sûrement quelques bugs.

C'est 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 *)];)
      ];

Principal

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 !

Edit : Recherche multi-angle

J'ai implémenté un changement dans l'algorithme permettant de chercher dans toutes les directions, mais en donnant la préférence à l'axe imposé par la symétrie géométrique.
Au prix d'un plus grand nombre de cycles, cela a permis d'obtenir des configurations finales plus compactes, comme vous pouvez le voir ci-dessous :

Plus d'échantillons aquí .

Le pseudo-code de la boucle principale a été modifié comme suit :

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

Je n'inclus pas le code source pour des raisons de brièveté, mais demandez-le si vous pensez pouvoir l'utiliser. Je pense que, si vous suivez cette voie, il est préférable de passer aux arbres R (beaucoup de tests d'intervalle sont nécessaires ici).

Answer 2

J'ai une idée.

Trouvez le centre C de la boîte de délimitation de vos rectangles.

Pour chaque rectangle R qui en recouvre un autre.

1. Définir un vecteur de mouvement v.
2. Trouvez tous les rectangles R' qui recouvrent R.
3. Ajouter à v un vecteur proportionnel au vecteur entre le centre de R et R'.
4. Ajouter à v un vecteur proportionnel au vecteur entre C et le centre de R.
5. Déplacez R par v.
6. Répétez jusqu'à ce que rien ne se chevauche.

Cela permet d'éloigner progressivement les rectangles les uns des autres et le centre de tous les rectangles. Cela se terminera parce que la composante de v de l'étape 4 finira par les écarter suffisamment par elle-même.

Answer 3

Je pense que cette solution est assez similaire à celle donnée par cape1232, mais elle est déjà implémentée, donc ça vaut le coup de vérifier :)

Suivez cette discussion sur Reddit : http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/ et consultez la description et l'implémentation. Il n'y a pas de code source disponible, donc voici mon approche de ce problème en AS3 (fonctionne exactement de la même manière, mais garde les rectangles accrochés à la résolution de la grille) :

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

Answer 4

J'aime beaucoup l'implémentation de b005t3r ! Elle fonctionne dans mes cas de test, mais ma réputation est trop faible pour laisser un commentaire avec les 2 corrections suggérées.

1. Vous ne devriez pas traduire les pièces par des incréments de résolution uniques, mais par la vitesse que vous venez de calculer avec précision ! Cela rend la séparation plus organique, car les pièces qui se croisent profondément se séparent davantage à chaque itération que celles qui ne se croisent pas profondément.

2. Vous ne devez pas supposer que des vélocités inférieures à 0,5 signifient que les pièces sont séparées, car vous pouvez vous retrouver dans un cas où vous n'êtes jamais séparé. Imaginez que deux pièces se croisent, mais qu'elles sont incapables de se corriger parce qu'à chaque fois que l'une ou l'autre tente de corriger la pénétration, elles calculent que la vitesse requise est < 0,5, ce qui les fait itérer sans fin.

Voici une solution Java ( : A la vôtre !

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

Answer 5

Voici un algorithme écrit en Java pour traiter une grappe de données non tournées. Rectangle s. Il vous permet de spécifier le rapport d'aspect souhaité de la mise en page et positionne le cluster à l'aide d'une méthode paramétrée. Rectangle comme point d'ancrage, autour duquel toutes les translations effectuées sont orientées. Vous pouvez également spécifier une quantité arbitraire de remplissage que vous souhaitez répartir dans l'ensemble de l'image. Rectangle par.

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

}

Voici un exemple utilisant un AspectRatio de 1.2 , a FillPercentage de 0.8 et un Padding de 10.0 .

Il s'agit d'une approche déterministe qui permet à l'espacement de se produire autour de l'ancre tout en laissant l'emplacement de l'ancre lui-même inchangé. Cela permet à la mise en page de se produire autour de l'endroit où se trouve le point d'intérêt de l'utilisateur. La logique de sélection d'une position est assez simpliste, mais je pense que l'architecture environnante, qui consiste à trier les éléments en fonction de leur position initiale puis à les itérer, est une approche utile pour mettre en œuvre une distribution relativement prévisible. De plus, nous ne nous appuyons pas sur des tests d'intersection itératifs ou sur quoi que ce soit de ce genre, nous nous contentons de construire des boîtes de délimitation pour nous donner une indication générale de l'endroit où aligner les choses ; après cela, l'application du remplissage se fait naturellement.