[Algorithm] Un algoritmo per distanziare i rettangoli sovrapposti?



Answers

Ecco un'ipotesi.

Trova il centro C del rettangolo di selezione dei tuoi rettangoli.

Per ogni rettangolo R che si sovrappone a un altro.

  1. Definire un vettore di movimento v.
  2. Trova tutti i rettangoli R 'che si sovrappongono a R.
  3. Aggiungi un vettore a v proporzionale al vettore tra il centro di R e R '.
  4. Aggiungi un vettore a v proporzionale al vettore tra C e il centro di R.
  5. Sposta R di v.
  6. Ripeti fino a quando non si sovrappone nulla.

Questo sposta in modo incrementale i rettangoli l'uno dall'altro e il centro di tutti i rettangoli. Questo finirà perché il componente di v dal passo 4 alla fine li distribuirà abbastanza da solo.

Question

Questo problema riguarda in realtà i rollover, mi limiterò a generalizzare in quanto tale:

Ho una vista 2D e ho un numero di rettangoli all'interno di un'area sullo schermo. Come faccio a diffondere quelle scatole in modo tale che non si sovrappongano l'una all'altra, ma solo regolarle con uno spostamento minimo?

Le posizioni dei rettangoli sono dinamiche e dipendono dall'input dell'utente, quindi le loro posizioni potrebbero essere ovunque.

Allegato le immagini mostrano il problema e la soluzione desiderata

Il vero problema della vita riguarda i rollover, in realtà.

Risposte alle domande nei commenti

  1. La dimensione dei rettangoli non è fissa e dipende dalla lunghezza del testo nel rollover

  2. A proposito delle dimensioni dello schermo, al momento penso sia meglio presumere che la dimensione dello schermo sia sufficiente per i rettangoli. Se ci sono troppi rettangoli e l'algo non produce soluzione, allora devo solo modificare il contenuto.

  3. L'esigenza di "spostare minimamente" è più per l'etica che per un requisito ingegneristico assoluto. Uno potrebbe distanziare due rettangoli aggiungendo una grande distanza tra loro, ma non sembrerà buono come parte della GUI. L'idea è di ottenere il rollover / il rettangolo il più vicino possibile alla sua sorgente (che poi collegherò alla sorgente con una linea nera). Quindi o 'spostare solo uno per x' o 'spostare entrambi per metà x' va bene.




Mi piace molto l'implementazione di b005t3r! Funziona nei miei casi di test, tuttavia il mio rappresentante è troppo basso per lasciare un commento con le 2 correzioni suggerite.

  1. Non dovresti tradurre stanze con incrementi a risoluzione singola, dovresti tradurre con la velocità che hai appena calcolato stazionariamente! Ciò rende la separazione più organica in quanto le sale profondamente intersecate separano più ogni iterazione rispetto alle stanze che non si intersecano così profondamente.

  2. Non dovresti pensare che i minuti meno di 0.5 significino che le stanze sono separate, in quanto puoi rimanere bloccato in un caso in cui non sei mai separato. Immaginate che 2 stanze si intersecano, ma non sono in grado di correggersi perché ogni volta che uno tenta di correggere la penetrazione, calcola la velocità richiesta come <0,5 in modo da iterare all'infinito.

Ecco una soluzione 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);



Ecco una versione che accetta la risposta di cape1232 ed è un esempio eseguibile standalone per 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();

            }
        });
    }

}





Links