Un algorithme pour espacer les rectangles qui se chevauchent?

Ce problème concerne en fait les roll-overs, je vais simplement les généraliser ci-dessous:

J’ai une vue en 2D et j’ai un certain nombre de rectangles dans une zone de l’écran. Comment répartir ces boîtes de manière à ce qu’elles ne se chevauchent pas, mais à les ajuster uniquement avec un minimum de mouvement?

Les positions des rectangles sont dynamics et dépendent de la saisie de l’utilisateur, donc leurs positions peuvent être n’importe où.

Attaché texte alt 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 dans le survol

  2. À propos de la taille de l’écran, 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, alors je dois juste modifier le contenu.

  3. L’exigence de «se déplacer de manière minimale» est davantage une exigence d’asthétique qu’une exigence d’ingénierie absolue. On peut espacer deux rectangles en ajoutant une grande distance entre eux, mais cela ne sera pas une bonne image dans l’interface graphique. L’idée est d’obtenir un rollover / rectangle aussi proche de sa source (que je connecterai ensuite à la source avec une ligne noire). Donc, soit “déplacer juste un pour x” ou “déplacer les deux pour moitié x” est bien.

Je travaillais 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é à obtenir une impulsion: D

J’avais aussi besoin du code source, alors le voici. Je l’ai développé dans Mathematica, mais comme je n’ai pas beaucoup utilisé les fonctionnalités, je suppose que ce sera facile à 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 des centres et des rayons.

J’ai pu utiliser le résolveur d’équations Mathematica, et cela s’est très bien passé.

Il suffit de regarder:

texte alt

C’était facile. Je viens de charger le solveur avec le problème suivant:

For each circle Solve[ Find new coördinates for the circle Minimizing the distance to the geomesortingc 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 geomesortingc center of the drawing ] 

Aussi simple que cela, et Mathematica a fait tout le travail.

J’ai dit “Ha! C’est facile, maintenant allons-y pour les rectangles!”. Mais je me trompais …

Blues Rectangulars

Le principal problème avec les rectangles est que l’interrogation de l’intersection est une mauvaise fonction. Quelque chose comme:

Donc, quand j’ai essayé de nourrir Mathematica avec beaucoup de ces conditions pour l’équation, ça a tellement mal fonctionné que j’ai décidé de faire quelque chose de procédural.

Mon algorithme s’est terminé 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 pop rectangle from stack and re-insert it into list find the geomesortingc 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 “plus petit mouvement” n’est pas complètement satisfaite (seulement dans une direction). Mais j’ai trouvé que déplacer les rectangles dans n’importe quelle direction pour le satisfaire aboutissait parfois à un changement de carte déroutant pour l’utilisateur.

Lorsque 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 changer l’algorithme pour inspecter tous les angles et tous les rayons entourant sa position actuelle jusqu’à ce qu’un endroit vide soit trouvé, bien que cela soit beaucoup plus exigeant.

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

texte alt

Modifier> Plus d’exemples ici

Comme vous pouvez le voir, le “mouvement minimum” n’est pas satisfait, mais les résultats sont assez bons.

Je posterai le code ici parce que j’ai des problèmes avec mon repository SVN. Je vais l’enlever lorsque les problèmes seront résolus.

Modifier:

Vous pouvez également utiliser R-Trees pour trouver des intersections de rectangle, mais il semble exagéré de traiter un petit nombre de rectangles. Et je n’ai pas encore implémenté les algorithmes. Quelqu’un d’autre peut peut-être vous indiquer une implémentation existante sur votre plate-forme de choix.

Attention! Le code est une première approche .. pas encore de grande qualité, et a sûrement des 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 *)];) ]; 

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!

Edit: Recherche multi-angle

J'ai implémenté une modification de l'algorithme permettant de rechercher dans toutes les directions, mais en privilégiant l'axe imposé par la symésortinge géomésortingque.
Au prix de plusieurs cycles, cela a abouti à des configurations finales plus compactes, comme vous pouvez le voir ci-dessous:

entrer la description de l'image ici

Plus d'échantillons ici .

Le pseudo-code de la boucle principale a été changé pour:

 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 geomesortingc 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 être bref, mais demandez-le simplement si vous pensez pouvoir l'utiliser. Je pense que, si vous allez dans cette direction, il est préférable de passer à R-trees (beaucoup de tests d'intervalle nécessaires ici)

Voici une supposition.

Trouvez le centre C de la boîte englobante de vos rectangles.

Pour chaque rectangle R qui en chevauche un autre.

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

Cela déplace progressivement les rectangles les uns des autres et le centre de tous les rectangles. Cela se terminera parce que le composant de v de l’étape 4 finira par les diffuser tout seul.

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

Suivez cette discussion sur la reddit: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/ et consultez la description et la mise en œuvre. Il n’y a pas de code source disponible, alors voici mon approche de ce problème dans AS3 (fonctionne exactement de la même manière, mais conserve les rectangles accrochés à la résolution de la grid):

 public class RoomSeparator extends AbstractAction { public function RoomSeparator(name:Ssortingng = "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; } } } } 

J’aime vraiment l’implémentation de b005t3r! Cela fonctionne dans mes cas de test, cependant mon représentant est trop faible pour laisser un commentaire avec les 2 corrections suggérées.

  1. Vous ne devriez pas traduire des pièces par incréments de résolution unique, vous devriez traduire par la vitesse que vous venez de calculer de manière difficile! Cela rend la séparation plus organique car les pièces profondément intersectées séparent plus chaque itération que les pièces qui ne se croisent pas si profondément.

  2. Vous ne devez pas supposer que les vélocités inférieures à 0,5 signifient que les pièces sont séparées car vous pouvez restr coincé dans un cas où vous n’êtes jamais séparé. Imaginez 2 pièces qui se croisent, mais qui sont incapables de se corriger, car chaque fois que l’une des deux tente de corriger la pénétration, elle calcule la vitesse requirejse à <0,5 pour qu'elles itèrent sans fin.

Voici une solution 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); 

Voici un algorithme écrit en Java pour gérer un cluster de Rectangle noté. Il vous permet de spécifier le format d’image souhaité de la mise en page et positionne le cluster à l’aide d’un Rectangle paramétré comme point d’ancrage, sur lequel toutes les traductions sont orientées. Vous pouvez également spécifier une quantité arbitraire de remplissage que vous souhaitez utiliser pour étendre le Rectangle s.

 public final class BoxxyDissortingbution { /* 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[BoxxyDissortingbution.INDEX_BOUNDS_MINIMUM_X], pMinimumX); pEnclosingBounds[1] = Math.min(pEnclosingBounds[BoxxyDissortingbution.INDEX_BOUNDS_MINIMUM_Y], pMinimumY); pEnclosingBounds[2] = Math.max(pEnclosingBounds[BoxxyDissortingbution.INDEX_BOUNDS_MAXIMUM_X], pMaximumX); pEnclosingBounds[3] = Math.max(pEnclosingBounds[BoxxyDissortingbution.INDEX_BOUNDS_MAXIMUM_Y], pMaximumY); } private static final void onEncapsulateBounds(final double[] pEnclosingBounds, final double[] pBounds) { BoxxyDissortingbution.onEncapsulateBounds(pEnclosingBounds, pBounds[BoxxyDissortingbution.INDEX_BOUNDS_MINIMUM_X], pBounds[BoxxyDissortingbution.INDEX_BOUNDS_MINIMUM_Y], pBounds[BoxxyDissortingbution.INDEX_BOUNDS_MAXIMUM_X], pBounds[BoxxyDissortingbution.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 onBoxxyDissortingbution(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 = BoxxyDissortingbution.onCalculateMagnitude(pAnchor.getCenterX() - pT0.getCenterX(), pAnchor.getCenterY() - pT0.getCenterY()); final double lDistance1 = BoxxyDissortingbution.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[BoxxyDissortingbution.INDEX_BOUNDS_MAXIMUM_X] - lTotalBounds[BoxxyDissortingbution.INDEX_BOUNDS_MINIMUM_X]))) { /* Register that the Rectangle IsBounded. */ lIsBounded = true; /* Update the Rectangle's X and Y Co-ordinates. */ lRectangle.setFrame((lRectangle.getX() > BoxxyDissortingbution.onCalculateMidpoint(lBounds[BoxxyDissortingbution.INDEX_BOUNDS_MAXIMUM_X], lBounds[BoxxyDissortingbution.INDEX_BOUNDS_MINIMUM_X])) ? lBounds[BoxxyDissortingbution.INDEX_BOUNDS_MAXIMUM_X] + pPadding : lBounds[BoxxyDissortingbution.INDEX_BOUNDS_MINIMUM_X] - (pPadding + lRectangle.getWidth()), lBounds[1], lRectangle.getWidth(), lRectangle.getHeight()); /* Update the Bounds. (Do not modify the vertical mesortingcs.) */ BoxxyDissortingbution.onEncapsulateBounds(lTotalBounds, lRectangle.getX(), lBounds[BoxxyDissortingbution.INDEX_BOUNDS_MINIMUM_Y], lRectangle.getX() + lRectangle.getWidth(), lBounds[BoxxyDissortingbution.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 = BoxxyDissortingbution.onCalculateMidpoint(lTotalBounds[BoxxyDissortingbution.INDEX_BOUNDS_MAXIMUM_Y], lTotalBounds[BoxxyDissortingbution.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 , un FillPercentage de 0.8 et un Padding de 10.0 .

100 rectangles répartis et distribués au hasard.

Les 100 rectangles aléatoires distribués à l'aide de BoxxyDistribution.

Il s'agit d'une approche déterministe qui permet d'espacer les points d'ancrage tout en laissant inchangé l'emplacement de l'ancre. Cela permet à la mise en page de se produire partout 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 de sorting des éléments en fonction de leur position initiale et de leur itération est une approche utile pour mettre en œuvre une dissortingbution relativement prévisible. De plus, nous ne nous appuyons pas sur des tests d'intersection itératifs ou quelque chose du genre, nous construisons simplement des boîtes englobantes pour nous donner une indication générale de l'endroit où aligner les choses; Après cela, appliquer le rembourrage vient naturellement.

Voici une version qui prend la réponse de cape1232 et qui est un exemple autonome exécutable pour 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 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(Ssortingng[] args) { SwingUtilities.invokeLater(new Runnable() { @Override public void run() { createAndShowGUI(); } }); } }