一个algorithm来分隔重叠的矩形？

这个问题实际上涉及到翻转，我将在下面概括如下：

我有一个2D视图，并在屏幕上的区域内有一些矩形。 我该如何分开那些不相互重叠的盒子，而只是用最小的移动来调整它们呢？

矩形的位置是dynamic的，取决于用户的input，所以它们的位置可以在任何地方。

附 图像显示问题和所需的解决scheme

真正的生活问题实际上是处理翻滚。

回答评论中的问题

1. 矩形的大小是不固定的，并且取决于翻转中文本的长度

2. 关于屏幕尺寸，现在我认为最好假设屏幕的尺寸足够矩形。 如果有太多的矩形和algorithm没有解决scheme，那么我只需要调整内容。

3. “最小限度地移动”的要求比绝对的工程要求更适合美学。 通过在两个矩形之间增加一个很大的距离，可以划出两个矩形，但是作为GUI的一部分，它看起来不太好。 这个想法是让翻转/矩形尽可能靠近它的源头（然后我用黑线连接到源）。 所以无论是“只移动一个x”还是“移动两个x”都没问题。

Answer 1

我在这方面做了一些工作，因为我也需要类似的东西，但是我推迟了algorithm的开发。 你帮助我得到一些冲动：D

我也需要源代码，所以在这里。 我在Mathematica中完成了这个工作，但是由于我没有使用过多的function特性，所以我想很容易翻译成任何过程语言。

一个历史的视angular

首先我决定开发圆的algorithm，因为交点更容易计算。 这只取决于中心和半径。

我能够使用Mathematica方程求解器，而且performance很好。

只是看看：

很容易。 我刚刚加载解决以下问题：

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提供这些条件的很多条件时，它performance得非常糟糕，所以我决定做一些程序。

我的algorithm结束如下：

 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 

你可能注意到“最小的运动”条件并不完全满足（只在一个方向上）。 但是我发现，将矩形向任何方向移动以满足它，有时最终会为用户改变一个令人困惑的地图。

当我devise用户界面时，我select将矩形稍微移动一点，但是以更可预测的方式。 您可以更改algorithm来检查所有angular度以及围绕其当前位置的所有半径，直到find一个空的位置，但要求更高。

无论如何，这些是结果的例子（之前/之后）：

编辑>更多的例子在这里

正如你所看到的，“最小的运动”并不满足，但结果是足够好的。

我会在这里发布代码，因为我的SVN存储库遇到了一些问题。 问题解决后我会将其删除。

编辑：

你也可以使用R-Trees来find矩形的交点，但是对于处理less量的矩形来说似乎是一种矫枉过正。 而且我还没有已经实现的algorithm。 也许别人可以指出你在你select的平台上现有的实现。

警告！ 代码是第一种方法..不是很好的质量，肯定有一些错误。

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

主要

 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！

编辑：多angular度search

我在algorithm中实现了一个更改，可以在所有方向上进行search，但优先考虑由几何对称性强加的轴。
以更多的周期为代价，这导致了更紧凑的最终configuration，如下所示：

更多样品在这里 。

主循环的伪代码变为：

 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树（这里需要很多的间隔testing）

Answer 2

这是一个猜测。

find矩形边界框的中心C.

对于每个与另一个重叠的矩形R。

1. 定义一个运动vectorv。
2. 找出所有与R重叠的矩形R'
3. 向v添加一个向量，与R和R'中心之间的向量成比例。
4. 添加一个向量与v和C中心之间的向量成正比。
5. 将v移动到v。
6. 重复，直到没有重叠。

这增加了矩形彼此之间的距离和所有矩形的中心。 这将终止，因为步骤4中v的组件最终将自行分散。

Answer 3

我觉得这个解决scheme和cape1232的解决scheme非常相似，但已经实现了，所以值得检查:)

请参阅此讨论： http ： //www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/并检查说明和实施。 没有可用的源代码，所以这里是我在AS3中解决这个问题的方法（工作方式完全相同，但是保持矩形alignment网格的分辨率）：

 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

我真的很喜欢b005t3r的实现！ 它适用于我的testing用例，但是我的代表太低，不能用build议的2个修复程序留下评论。

1. 你不应该通过单一的分辨率增量翻译房间，你应该翻译的速度，你只是痛苦的计算！ 这使得分离更加有机，因为深度相交的房间每隔一个迭代就会比不太深的房间分隔更多。

2. 你不应该假设velociites小于0.5意味着房间是分开的，因为你可以卡在一个你永远不会分开的情况下。 设想2个房间相交，但无法自行纠正，因为无论何时尝试纠正渗透，他们计算所需的速度为<0.5，因此他们无止境地迭代。

这是一个Java解决scheme（：干杯！

 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

下面是一个采用cape1232的答案的版本，它是Java的一个独立的可运行示例：

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

Answer 6

下面是使用Java编写的用于处理未旋转Rectangle集群的algorithm。 它允许您指定所需的高宽比，并使用参数化的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<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()); } } } 

}

下面是一个使用1.2的AspectRatio ， 0.8的Padding FillPercentage和10.0的Padding的例子。

这是一种确定性的方法，允许在锚的周围发生间隔，同时保持锚本身的位置不变。 这允许布局发生在用户兴趣点的任何地方。 select一个职位的逻辑非常简单，但是我认为周围的基于初始职位的元素sorting架构，然后迭代他们是一个实现相对可预测的分配的有用的方法。 此外，我们不是依靠迭代交叉testing或类似的东西，只是build立一些边界框给我们一个广泛的指示，在哪里alignment的东西; 在此之后，填补只是自然而然的。