Алгоритм для выделения перекрывающихся прямоугольников?

Я немного работал над этим, так как мне также было нужно что-то подобное, но я отложил разработку алгоритма. Вы помогли мне получить импульс: D

Мне также нужен исходный код, так что вот оно. Я работал в Mathematica, но, поскольку я не использовал сильно функциональные функции, я думаю, это будет легко перевести на любой процедурный язык.

Историческая перспектива

Сначала я решил разработать алгоритм для кругов, потому что пересечение легче вычислить. Это зависит только от центров и радиусов.

Я смог использовать решатель уравнений Mathematica, и это было хорошо.

Взгляни:

Это было легко. Я просто загрузил решателя со следующей проблемой:

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 ] 

Как прямо, так и Mathematica выполнили всю работу.

Я сказал: «Ха! Это легко, теперь давайте пойдем за прямоугольники!». Но я был неправ …

Прямоугольный блюз

Основная проблема с прямоугольниками заключается в том, что запрос пересечения является неприятной функцией. Что-то вроде:

Итак, когда я попытался накормить Mathematica множеством этих условий для уравнения, он сделал так плохо, что я решил сделать что-то процедурное.

Мой алгоритм оказался следующим:

 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 

Вы можете заметить, что условие «наименьшего движения» не полностью удовлетворено (только в одном направлении). Но я обнаружил, что перемещение прямоугольников в любом направлении, чтобы удовлетворить его, иногда заканчивается запутанной картой, изменяющейся для пользователя.

Когда я проектирую пользовательский интерфейс, я предпочитаю перемещать прямоугольник немного дальше, но более предсказуемым образом. Вы можете изменить алгоритм, чтобы проверить все углы и все радиусы, окружающие его текущее положение, до тех пор, пока не будет найдено пустое место, хотя это будет гораздо более требовательным.

Во всяком случае, это примеры результатов (до / после):

Редактировать> Другие примеры здесь

Как вы можете видеть, «минимальное движение» не выполняется, но результаты достаточно хороши.

Я отправлю код здесь, потому что у меня возникают проблемы с моим репозиторием SVN. Я удалю его, когда проблемы будут решены.

Редактировать:

Вы также можете использовать R-Trees для поиска пересечений прямоугольников, но, похоже, это избыток для работы с небольшим количеством прямоугольников. И у меня нет уже реализованных алгоритмов. Возможно, кто-то еще может указать вам на существующую реализацию на вашей платформе выбора.

Предупреждение! Код – это первый подход. Не отличное качество, и, конечно же, есть некоторые ошибки.

Это Математика.

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

Главный

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

НТН!

Изменить: поиск по нескольким углам

Я внедрил изменение в алгоритме, позволяющем искать во всех направлениях, но отдавая предпочтение оси, налагаемой геометрической симметрией.
За счет большего количества циклов это привело к более компактным окончательным конфигурациям, как вы можете видеть ниже:

Здесь больше образцов.

Псевдокод для основного цикла изменился на:

 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 

Я не включаю исходный код для краткости, но просто прошу об этом, если вы думаете, что можете его использовать. Я думаю, что, если вы пойдете так, лучше переключиться на R-деревья (здесь нужно много интервальных тестов)

Вот догадка.

Найдите центр C ограничивающего прямоугольника ваших прямоугольников.

Для каждого прямоугольника R, который перекрывает другой.

1. Определить вектор движения v.
2. Найдите все прямоугольники R ‘, которые перекрывают R.
3. Добавьте вектор к v, пропорциональный вектору между центром R и R ‘.
4. Добавьте вектор к v, пропорциональный вектору между C и центром R.
5. Переместите R на v.
6. Повторяйте, пока ничего не перекрывается.

Это постепенно перемещает прямоугольники друг от друга и центр всех прямоугольников. Это закончится, потому что компонент v из шага 4 в конечном итоге будет достаточно распространять их самостоятельно.

Я думаю, что это решение очень похоже на то, что дается cape1232, но оно уже реализовано, поэтому стоит проверить:

Следуйте за этим красным обсуждением: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/ и ознакомьтесь с описанием и реализацией. Нет исходного кода, поэтому вот мой подход к этой проблеме в AS3 (работает точно так же, но сохраняет прямоугольники, привязанные к разрешению сетки):

 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! Он работает в моих тестовых случаях, однако мой репорт слишком низок, чтобы оставить комментарий с двумя предложенными исправлениями.

1. Вы не должны переводить комнаты с шагом в один разрез, вы должны перевести на скорость, которую вы просто потратили на тотализацию! Это делает разделение более органичным, поскольку глубоко пересеченные комнаты больше разделяют каждую итерацию, чем не слишком глубоко пересекающиеся комнаты.

2. Вы не должны предполагать, что скорость меньше 0,5 означает, что комнаты являются отдельными, так как вы можете застревать в случае, когда вы никогда не разделяетесь. Представьте, что 2 комнаты пересекаются, но не могут исправить себя, потому что всякий раз, когда кто-либо пытается исправить проникновение, они вычисляют требуемую скорость как <0,5, поэтому они повторяются бесконечно.

Вот 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); 

Вот алгоритм, написанный с использованием Java для обработки кластера невращающихся Rectangle s. Это позволяет определить нужное соотношение сторон макета и позиционирует кластер , используя параметризованный Rectangle в качестве точки привязки, который все переводы , выполненные ориентированы о. Вы также можете указать произвольное количество отступов, которое вы хотите распространить на Rectangle .

 public final class BoxxyDistribution { /* Static Definitions. */ private static final int INDEX_BOUNDS_MINIMUM_X = 0; private static final int INDEX_BOUNDS_MINIMUM_Y = 1; private static final int INDEX_BOUNDS_MAXIMUM_X = 2; private static final int INDEX_BOUNDS_MAXIMUM_Y = 3; private static final double onCalculateMagnitude(final double pDeltaX, final double pDeltaY) { return Math.sqrt((pDeltaX * pDeltaX) + (pDeltaY + pDeltaY)); } /* Updates the members of EnclosingBounds to ensure the dimensions of T can be completely encapsulated. */ private static final void onEncapsulateBounds(final double[] pEnclosingBounds, final double pMinimumX, final double pMinimumY, final double pMaximumX, final double pMaximumY) { pEnclosingBounds[0] = Math.min(pEnclosingBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X], pMinimumX); pEnclosingBounds[1] = Math.min(pEnclosingBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y], pMinimumY); pEnclosingBounds[2] = Math.max(pEnclosingBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X], pMaximumX); pEnclosingBounds[3] = Math.max(pEnclosingBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y], pMaximumY); } private static final void onEncapsulateBounds(final double[] pEnclosingBounds, final double[] pBounds) { BoxxyDistribution.onEncapsulateBounds(pEnclosingBounds, pBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X], pBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y], pBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X], pBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y]); } private static final double onCalculateMidpoint(final double pMaximum, final double pMinimum) { return ((pMaximum - pMinimum) * 0.5) + pMinimum; } /* Re-arranges a List of Rectangles into something aesthetically pleasing. */ public static final void onBoxxyDistribution(final List pRectangles, final Rectangle pAnchor, final double pPadding, final double pAspectRatio, final float pRowFillPercentage) { /* Create a safe clone of the Rectangles that we can modify as we please. */ final List lRectangles = new ArrayList(pRectangles); /* Allocate a List to track the bounds of each Row. */ final List lRowBounds = new ArrayList(); // (MinX, MinY, MaxX, MaxY) /* Ensure Rectangles does not contain the Anchor. */ lRectangles.remove(pAnchor); /* Order the Rectangles via their proximity to the Anchor. */ Collections.sort(pRectangles, new Comparator(){ @Override public final int compare(final Rectangle pT0, final Rectangle pT1) { /* Calculate the Distance for pT0. */ final double lDistance0 = BoxxyDistribution.onCalculateMagnitude(pAnchor.getCenterX() - pT0.getCenterX(), pAnchor.getCenterY() - pT0.getCenterY()); final double lDistance1 = BoxxyDistribution.onCalculateMagnitude(pAnchor.getCenterX() - pT1.getCenterX(), pAnchor.getCenterY() - pT1.getCenterY()); /* Compare the magnitude in distance between the anchor and the Rectangles. */ return Double.compare(lDistance0, lDistance1); } }); /* Initialize the RowBounds using the Anchor. */ /** TODO: Probably better to call getBounds() here. **/ lRowBounds.add(new double[]{ pAnchor.getX(), pAnchor.getY(), pAnchor.getX() + pAnchor.getWidth(), pAnchor.getY() + pAnchor.getHeight() }); /* Allocate a variable for tracking the TotalBounds of all rows. */ final double[] lTotalBounds = new double[]{ Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY }; /* Now we iterate the Rectangles to place them optimally about the Anchor. */ for(int i = 0; i < lRectangles.size(); i++) { /* Fetch the Rectangle. */ final Rectangle lRectangle = lRectangles.get(i); /* Iterate through each Row. */ for(final double[] lBounds : lRowBounds) { /* Update the TotalBounds. */ BoxxyDistribution.onEncapsulateBounds(lTotalBounds, lBounds); } /* Allocate a variable to state whether the Rectangle has been allocated a suitable RowBounds. */ boolean lIsBounded = false; /* Calculate the AspectRatio. */ final double lAspectRatio = (lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X] - lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X]) / (lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y] - lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y]); /* We will now iterate through each of the available Rows to determine if a Rectangle can be stored. */ for(int j = 0; j < lRowBounds.size() && !lIsBounded; j++) { /* Fetch the Bounds. */ final double[] lBounds = lRowBounds.get(j); /* Calculate the width and height of the Bounds. */ final double lWidth = lBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X] - lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X]; final double lHeight = lBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y] - lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y]; /* Determine whether the Rectangle is suitable to fit in the RowBounds. */ if(lRectangle.getHeight() <= lHeight && !(lAspectRatio > pAspectRatio && lWidth > pRowFillPercentage * (lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X] - lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X]))) { /* Register that the Rectangle IsBounded. */ lIsBounded = true; /* Update the Rectangle's X and Y Co-ordinates. */ lRectangle.setFrame((lRectangle.getX() > BoxxyDistribution.onCalculateMidpoint(lBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X], lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X])) ? lBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_X] + pPadding : lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X] - (pPadding + lRectangle.getWidth()), lBounds[1], lRectangle.getWidth(), lRectangle.getHeight()); /* Update the Bounds. (Do not modify the vertical metrics.) */ BoxxyDistribution.onEncapsulateBounds(lTotalBounds, lRectangle.getX(), lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y], lRectangle.getX() + lRectangle.getWidth(), lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y] + lHeight); } } /* Determine if the Rectangle has not been allocated a Row. */ if(!lIsBounded) { /* Calculate the MidPoint of the TotalBounds. */ final double lCentreY = BoxxyDistribution.onCalculateMidpoint(lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y], lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y]); /* Determine whether to place the bounds above or below? */ final double lYPosition = lRectangle.getY() < lCentreY ? lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y] - (pPadding + lRectangle.getHeight()) : (lTotalBounds[BoxxyDistribution.INDEX_BOUNDS_MAXIMUM_Y] + pPadding); /* Create a new RowBounds. */ final double[] lBounds = new double[]{ pAnchor.getX(), lYPosition, pAnchor.getX() + lRectangle.getWidth(), lYPosition + lRectangle.getHeight() }; /* Allocate a new row, roughly positioned about the anchor. */ lRowBounds.add(lBounds); /* Position the Rectangle. */ lRectangle.setFrame(lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_X], lBounds[BoxxyDistribution.INDEX_BOUNDS_MINIMUM_Y], lRectangle.getWidth(), lRectangle.getHeight()); } } } 

}

Вот пример использования AspectRatio 1.2 , FillPercentage 0.8 и Padding 10.0 .

Это детерминированный подход, который позволяет проводить интервал вокруг якоря, оставляя без изменения местоположение самого якоря. Это позволяет размещать макет везде, где находится Точка интереса пользователя. Логика выбора позиции довольно упрощена, но я думаю, что окружающая архитектура сортировки элементов, основанных на их исходном положении, а затем их итерации - полезный подход для реализации относительно outlookируемого распределения. Плюс мы не полагаемся на итеративные тесты пересечения или что-то в этом роде, просто создавая некоторые ограничивающие прямоугольники, чтобы дать нам широкое указание на то, где выровнять вещи; после этого, применение прокладки просто приходит вроде естественно.

Вот версия, которая берет ответ cape1232 и является автономным исполняемым примером 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(String[] args) { SwingUtilities.invokeLater(new Runnable() { @Override public void run() { createAndShowGUI(); } }); } }