algorithm - ¿Un algoritmo para espaciar los rectángulos superpuestos?

user-interface language-agnostic

Question

Este problema en realidad se ocupa de los roll-overs, voy a generalizar a continuación como tal:

Tengo una vista 2D, y tengo una cantidad de rectángulos dentro de un área en la pantalla. ¿Cómo extiendo esas cajas para que no se superpongan entre sí, sino que las ajuste con un mínimo de movimiento?

Las posiciones de los rectángulos son dinámicas y dependen de la entrada del usuario, por lo que sus posiciones podrían estar en cualquier lugar.

Adjunto las imágenes muestran el problema y la solución deseada

El problema de la vida real se trata de reinversiones, en realidad.

Respuestas a las preguntas en los comentarios

1. El tamaño de los rectángulos no es fijo, y depende de la longitud del texto en el rollover

2. Sobre el tamaño de la pantalla, ahora mismo creo que es mejor suponer que el tamaño de la pantalla es suficiente para los rectángulos. Si hay demasiados rectángulos y el algo no produce solución, entonces solo tengo que ajustar el contenido.

3. El requisito de ''moverse mínimamente'' es más para asetéticos que un requisito de ingeniería absoluto. Uno podría espaciar dos rectángulos al agregar una gran distancia entre ellos, pero no se verá bien como parte de la GUI. La idea es hacer que el rollover / rectángulo esté tan cerca de su fuente (que luego conectaré a la fuente con una línea negra). Entonces, o bien ''moviendo solo uno para x'' o ''moviendo ambos para la mitad x'' está bien.

Answer 1

¡Realmente me gusta la implementación de b005t3r! Funciona en mis casos de prueba, sin embargo, mi representante es demasiado bajo para dejar un comentario con las 2 soluciones sugeridas.

1. No deberías traducir habitaciones por incrementos de resolución únicos, ¡debes traducir por la velocidad que tan dolorosamente calculaste! Esto hace que la separación sea más orgánica ya que las habitaciones profundamente intersecadas separan más cada iteración que las habitaciones que no se intersecan tan profundamente.

2. No debe suponer velocidades inferiores a 0.5 significa que las habitaciones están separadas, ya que puede quedar atascado en un caso en el que nunca se separa. Imagínese que 2 habitaciones se intersecan, pero no pueden corregirse porque cada vez que uno trata de corregir la penetración, calculan la velocidad requerida como <0.5, por lo que iteran interminablemente.

Aquí hay una solución Java (: ¡Salud!

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 2

Aquí hay un algoritmo escrito usando Java para manejar un grupo de Rectangle no Rectangle . Le permite especificar la relación de aspecto deseada del diseño y posiciona el clúster utilizando un Rectangle parametrizado como punto de anclaje, sobre el que están orientadas todas las traducciones realizadas. También puede especificar una cantidad arbitraria de relleno para la cual le gustaría extender los 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());
        }
    }
}

}

Aquí hay un ejemplo con una AspectRatio de 1.2 , un FillPercentage de 0.8 y un Padding de 10.0 .

Este es un enfoque determinista que permite que se produzca un espaciado alrededor del anclaje, sin modificar la ubicación del anclaje. Esto permite que el diseño se produzca alrededor del punto de interés del usuario. La lógica para seleccionar una posición es bastante simplista, pero creo que la arquitectura circundante de ordenar los elementos en función de su posición inicial y luego iterarlos es un enfoque útil para implementar una distribución relativamente predecible. Además, no estamos confiando en pruebas de intersección iterativas ni nada de eso, simplemente construyendo algunos cuadros delimitadores para darnos una amplia indicación de dónde alinear las cosas; después de esto, la aplicación de relleno viene naturalmente.

Answer 3

Aquí hay una conjetura.

Encuentra el centro C del cuadro delimitador de tus rectángulos.

Para cada rectángulo R que se superpone a otro.

1. Definir un vector de movimiento v.
2. Encuentra todos los rectángulos R ''que se superponen R.
3. Agregue un vector a v proporcional al vector entre el centro de R y R ''.
4. Agregue un vector a v proporcional al vector entre C y el centro de R.
5. Mover R por v.
6. Repita hasta que nada se solape.

Esto mueve los rectángulos de distancia uno del otro y del centro de todos los rectángulos. Esto terminará porque el componente de v del paso 4 eventualmente los dispersará por sí solo.

Answer 4

Aquí hay una versión que toma la respuesta de cape1232 y es un ejemplo ejecutable independiente para 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 5

Creo que esta solución es bastante similar a la que proporciona cape1232, pero ya está implementada, así que vale la pena echarle un vistazo :)

Siga a esta discusión de reddit: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/ y revise la descripción y la implementación. No hay ningún código fuente disponible, así que aquí está mi enfoque de este problema en AS3 (funciona exactamente igual, pero mantiene los rectángulos ajustados a la resolución de la cuadrícula):

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 6

Estaba trabajando un poco en esto, ya que también necesitaba algo similar, pero había retrasado el desarrollo del algoritmo. Me ayudaste a tener algún impulso: D

También necesitaba el código fuente, así que aquí está. Lo resolví en Mathematica, pero como no he usado mucho las características funcionales, creo que será fácil traducirlo a cualquier lenguaje de procedimiento.

Una perspectiva histórica

Primero decidí desarrollar el algoritmo para círculos, porque la intersección es más fácil de calcular. Solo depende de los centros y radios.

Pude utilizar el solucionador de ecuaciones de Mathematica, y funcionó muy bien.

Solo mira:

Fue fácil. Acabo de cargar el solucionador con el siguiente problema:

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
   ]

Tan sencillo como eso, y Mathematica hizo todo el trabajo.

Dije "¡Ja! ¡Es fácil, ahora vamos por los rectángulos!". Pero estaba equivocado ...

Blues rectangular

El principal problema con los rectángulos es que consultar la intersección es una función desagradable. Algo como:

Entonces, cuando traté de alimentar a Mathematica con muchas de estas condiciones para la ecuación, funcionó tan mal que decidí hacer algo de procedimiento.

Mi algoritmo terminó de la siguiente manera:

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

Puede observar que la condición de "movimiento más pequeño" no está completamente satisfecha (solo en una dirección). Pero descubrí que mover los rectángulos en cualquier dirección para satisfacerlo, a veces termina con un cambio de mapa confuso para el usuario.

Como estoy diseñando una interfaz de usuario, elijo mover el rectángulo un poco más, pero de una manera más predecible. Puede cambiar el algoritmo para inspeccionar todos los ángulos y todos los radios que rodean su posición actual hasta encontrar un lugar vacío, aunque será mucho más exigente.

De todos modos, estos son ejemplos de los resultados (antes / después):

Editar> Más ejemplos here

Como puede ver, el "movimiento mínimo" no está satisfecho, pero los resultados son lo suficientemente buenos.

Publicaré el código aquí porque estoy teniendo problemas con mi repositorio SVN. Lo eliminaré cuando se resuelvan los problemas.

Editar:

También puede usar R-Trees para encontrar intersecciones de rectángulo, pero parece una exageración para tratar con una pequeña cantidad de rectángulos. Y no tengo los algoritmos ya implementados. Quizás alguien más pueda indicarle una implementación existente en su plataforma de elección.

¡Advertencia! El código es un primer enfoque ... aún no es de gran calidad, y seguramente tiene algunos errores.

Es Mathematica.

(*Define some functions first*)

Clear["Global`*"];
rn[x_] := RandomReal[{0, x}];
rnR[x_] := RandomReal[{1, x}];
rndCol[] := RGBColor[rn[1], rn[1], rn[1]];

minX[l_, i_] := l[[i]][[1]][[1]]; (*just for easy reading*)
maxX[l_, i_] := l[[i]][[1]][[2]];
minY[l_, i_] := l[[i]][[2]][[1]];
maxY[l_, i_] := l[[i]][[2]][[2]];
color[l_, i_]:= l[[i]][[3]];

intersectsQ[l_, i_, j_] := (* l list, (i,j) indexes, 
                              list={{x1,x2},{y1,y2}} *) 
                           (*A rect does intesect with itself*)
          If[Max[minX[l, i], minX[l, j]] < Min[maxX[l, i], maxX[l, j]] &&
             Max[minY[l, i], minY[l, j]] < Min[maxY[l, i], maxY[l, j]], 
                                                           True,False];

(* Number of Intersects for a Rectangle *)
(* With i as index*)
countIntersects[l_, i_] := 
          Count[Table[intersectsQ[l, i, j], {j, 1, Length[l]}], True]-1;

(*And With r as rectangle *)
countIntersectsR[l_, r_] := (
    Return[Count[Table[intersectsQ[Append[l, r], Length[l] + 1, j], 
                       {j, 1, Length[l] + 1}], True] - 2];)

(* Get the maximum intersections for all rectangles*)
findMaxIntesections[l_] := Max[Table[countIntersects[l, i], 
                                       {i, 1, Length[l]}]];

(* Get the rectangle center *)
rectCenter[l_, i_] := {1/2 (maxX[l, i] + minX[l, i] ), 
                       1/2 (maxY[l, i] + minY[l, i] )};

(* Get the Geom center of the whole figure (list), to move aesthetically*)
geometryCenter[l_] :=  (* returs {x,y} *)
                      Mean[Table[rectCenter[l, i], {i, Length[l]}]]; 

(* Increment or decr. size of all rects by a bit (put/remove borders)*)
changeSize[l_, incr_] :=
                 Table[{{minX[l, i] - incr, maxX[l, i] + incr},
                        {minY[l, i] - incr, maxY[l, i] + incr},
                        color[l, i]},
                        {i, Length[l]}];

sortListByIntersections[l_] := (* Order list by most intersecting Rects*)
        Module[{a, b}, 
               a = MapIndexed[{countIntersectsR[l, #1], #2} &, l];
               b = SortBy[a, -#[[1]] &];
               Return[Table[l[[b[[i]][[2]][[1]]]], {i, Length[b]}]];
        ];

(* Utility Functions*)
deb[x_] := (Print["--------"]; Print[x]; Print["---------"];)(* for debug *)
tableForPlot[l_] := (*for plotting*)
                Table[{color[l, i], Rectangle[{minX[l, i], minY[l, i]},
                {maxX[l, i], maxY[l, i]}]}, {i, Length[l]}];

genList[nonOverlap_, Overlap_] :=    (* Generate initial lists of rects*)
      Module[{alist, blist, a, b}, 
          (alist = (* Generate non overlapping - Tabuloid *)
                Table[{{Mod[i, 3], Mod[i, 3] + .8}, 
                       {Mod[i, 4], Mod[i, 4] + .8},  
                       rndCol[]}, {i, nonOverlap}];
           blist = (* Random overlapping *)
                Table[{{a = rnR[3], a + rnR[2]}, {b = rnR[3], b + rnR[2]}, 
                      rndCol[]}, {Overlap}];
           Return[Join[alist, blist] (* Join both *)];)
      ];

Principal

clist = genList[6, 4]; (* Generate a mix fixed & random set *)

incr = 0.05; (* may be some heuristics needed to determine best increment*)

clist = changeSize[clist,incr]; (* expand rects so that borders does not 
                                                         touch each other*)

(* Now remove all intercepting rectangles until no more intersections *)

workList = {}; (* the stack*)

While[findMaxIntesections[clist] > 0,          
                                      (*Iterate until no intersections *)
    clist    = sortListByIntersections[clist]; 
                                      (*Put the most intersected first*)
    PrependTo[workList, First[clist]];         
                                      (* Push workList with intersected *)
    clist    = Delete[clist, 1];      (* and Drop it from clist *)
];

(* There are no intersections now, lets pop the stack*)

While [workList != {},

    PrependTo[clist, First[workList]];       
                                 (*Push first element in front of clist*)
    workList = Delete[workList, 1];          
                                 (* and Drop it from worklist *)

    toMoveIndex = 1;                        
                                 (*Will move the most intersected Rect*)
    g = geometryCenter[clist];               
                                 (*so the geom. perception is preserved*)
    vectorToMove = rectCenter[clist, toMoveIndex] - g;
    If [Norm[vectorToMove] < 0.01, vectorToMove = {1,1}]; (*just in case*)  
    vectorToMove = vectorToMove/Norm[vectorToMove];      
                                            (*to manage step size wisely*)

    (*Now iterate finding minimum move first one way, then the other*)

    i = 1; (*movement quantity*)

    While[countIntersects[clist, toMoveIndex] != 0, 
                                           (*If the Rect still intersects*)
                                           (*move it alternating ways (-1)^n *)

      clist[[toMoveIndex]][[1]] += (-1)^i i incr vectorToMove[[1]];(*X coords*)
      clist[[toMoveIndex]][[2]] += (-1)^i i incr vectorToMove[[2]];(*Y coords*)

            i++;
    ];
];
clist = changeSize[clist, -incr](* restore original sizes*);

HTH!

Editar: búsqueda de ángulo múltiple

Implementé un cambio en el algoritmo que permite buscar en todas las direcciones, pero dando preferencia al eje impuesto por la simetría geométrica.
A expensas de más ciclos, esto dio como resultado configuraciones finales más compactas, como puede ver a continuación:

Más muestras here .

El pseudocódigo para el ciclo principal cambió a:

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

No incluyo el código fuente de brevedad, solo pídalo si crees que puedes usarlo. Creo que, si sigues este camino, es mejor cambiar a árboles R (se necesitan muchas pruebas de intervalo aquí)