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

Ответ 1

Я немного работал над этим, так как мне также было нужно что-то подобное, но я отложил разработку алгоритма. Вы помогли мне получить импульс: 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)^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*);

НТН!

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

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

Дополнительные образцы здесь.

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

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-деревья (здесь нужно много интервальных тестов)

Ответ 2

Вот догадка.

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

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

• Определить вектор движения v.
• Найдите все прямоугольники R ', которые перекрывают R.
• Добавьте вектор к v, пропорциональный вектору между центром R и R '.
• Добавьте вектор к v, пропорциональный вектору между C и центром R.
• Переместить R на v.
• Повторяйте, пока ничего не перекрывается.

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

Ответ 3

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

Следуйте за этим обсуждением в reddit: 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;
            }
        }
    }
}

Ответ 4

Мне очень нравится реализация b005t3r! Он работает в моих тестовых случаях, однако мой репорт слишком низок, чтобы оставить комментарий с двумя предложенными исправлениями.

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

• Вы не должны предполагать, что скорость меньше 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);

Ответ 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();

            }
        });
    }

}

Ответ 6

Вот алгоритм, написанный с использованием 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<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 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 of 1.2, a FillPercentage of 0.8 и a Padding of 10.0.

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