6
\$\begingroup\$

I've been working on an algorithm to declutter rectangles while keeping them as close as possible to their original location (and oriented the same way). It seems to work fine when I have less than 1,000 rectangles, but becomes much slower when there are 10,000, which I believe to be because the algorithm is inefficient with large datasets. I'm looking to find ways to optimize to perform better with more rectangles.

The code I have is based on this algorithm (which is based on this SO answer from another similar question: https://stackoverflow.com/a/3266158/33863):


Find the center C of the bounding box of your rectangles.

For each rectangle R that overlaps another:

  • Define a movement vector v.
  • Find all the rectangles R' that overlap R.
  • Add a vector to v proportional to the vector between the center of R and R'.
  • Add a vector to v proportional to the vector between C and the center of R.
  • Move R by v.
  • Repeat until nothing overlaps.

This incrementally moves the rectangles away from each other and the center of all the rectangles. This will terminate because the component of v from step 4 will eventually spread them out enough all by itself.


Here is the code I'm working with:

public class Rectangles extends JPanel {

    // Create sample rectangles laid out in frame
    List<Rectangle2D> rectangles = new ArrayList<Rectangle2D>();
    {
        // x,y,w,h
        // random rectangles
        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));
        rectangles.add(new Rectangle2D.Float(690, 229, 388, 114));
        rectangles.add(new Rectangle2D.Float(347, 341, 347, 425));
        rectangles.add(new Rectangle2D.Float(107, 515, 179, 158));
        rectangles.add(new Rectangle2D.Float(55, 487, 174, 153));
        rectangles.add(new Rectangle2D.Float(458, 553, 125, 128));
        rectangles.add(new Rectangle2D.Float(109, 566, 125, 128));
        rectangles.add(new Rectangle2D.Float(138, 166, 125, 128));


        int numRowsAndColumns = 20;
//      int numRowsAndColumns = 50;
//      int numRowsAndColumns = 100;
//      Add more rectangles
        for (int i = 0; i < numRowsAndColumns; i++) {
            for (int j = 0; j < numRowsAndColumns; j++) {
                rectangles.add(new Rectangle2D.Float(i * 20, j * 10, 25, 20));
            }
        }


        System.out.println("Num Rectangles " + rectangles.size());
    }

    //The list of rectangles that are drawn on the screen
    List<Rectangle2D> rectanglesToDraw;

    //reset the view back to the unaffected rectangles
    protected void reset() {
        rectanglesToDraw = rectangles;

        this.repaint();
    }

    //Given a rectangle, find the rectangles from the rectList that intersect with it
    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;
    }

    //main algorithm that attempts to declutter the rectangles.    
    protected void fix() {
        rectanglesToDraw = new ArrayList<Rectangle2D>();

        //make copies to keep original list unaffected
        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 numIterations = 0;

        int movementFactor = 10; //ideally would be 1

        boolean hasIntersections = true;

        //keep going until there are no intersections present    
        while (hasIntersections) {

            //initialize to false within the loop.  
            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;
                }

            }

            numIterations++;

        }

        System.out.println("That took " + numIterations+ " iterations.");

        Rectangles.this.repaint();

    }

    //find the Bounding rectangle of the list of rectangles
    //by iterating over all rectangles and 
    //finding the top left and bottom right corners
    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());
    }

    //Draws the rectangles in the frame from the rectanglesToDraw data structure  
    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);
        }

    }

    //create GUI components and display it to the user
    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) {

                long start = System.currentTimeMillis();
                rects.fix();
                long end = System.currentTimeMillis();

                System.out.println("That took "+TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.MILLISECONDS)+ " ms");

            }
        });

        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(1920, 900);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {

            @Override
            public void run() {
                createAndShowGUI();

            }
        });
    }

}

Here are a couple of screenshots to illustrate what its doing:

Before: Before

After: After

\$\endgroup\$
  • \$\begingroup\$ You present uncommented code. Please include a high-level description of the algorithm you use. The problem description screams divide and conquer. \$\endgroup\$ – greybeard Sep 23 '17 at 7:17
  • \$\begingroup\$ The hasIntersections boolean needs to be removed, or at least have a better usage. \$\endgroup\$ – T145 Sep 23 '17 at 7:50
  • \$\begingroup\$ I’ve added some comments and algorithm information \$\endgroup\$ – user149435 Sep 23 '17 at 23:18
  • \$\begingroup\$ …added … comments and algorithm information yes, but the goal and constraints aren't over-specified, yet. From what I gather, this resembles (single/intra-layer) Design Rule Adap(ta)tion - Magic may be a place to start. Strategically, you need to avoid "relating" parts too far apart to have mutual influence. Sweep line algorithms do this more dynamically than divide & conquer. \$\endgroup\$ – greybeard Sep 24 '17 at 23:45
  • 1
    \$\begingroup\$ I gave this some thought, but not enough to have a full solution. You could try to divide-and-conquer, but that would lead either to unappealing results, or at least O(n^2) complexity. Quadtrees might help, but it seems like that would still have other problems. I'm unsure of the complexity of your current algorithm, but I suspect it's somewhere around O(n^3) or O(n^2) (at least to a point where big-O doesn't really mean too much, as there are more variables). \$\endgroup\$ – Justin Sep 29 '17 at 22:13
3
+50
\$\begingroup\$

Not much of a code review, too long for a comment - suggestion:

Do a line sweep over your (iso-oriented ("axis-parallel")?) rectangles computing "vertical" and "horizontal" scales sufficient to declutter them as needed. (With identical y-coordinates or enclosure, adjust x-scaling and vice-versa. With overlap or enclosure in both directions, main concerns are current scales and relative amount of overlap. With identical mid-point, you're screwed.)
Scale everything as computed, eyeball the result and refine your requirement description.

\$\endgroup\$
  • \$\begingroup\$ Got paid for programming in that area for almost a decade - three decades and even more programming languages ago. Expect at least 999 hours for a decent design rule adaptation from scratch, with two or three orders of magnitude that for a competitive commercial offering. \$\endgroup\$ – greybeard Sep 25 '17 at 8:15
1
\$\begingroup\$

Not an algorithm review, but rather a review from software engineering point of view.

Advice 1

List<Rectangle2D> rectangles = new ArrayList<Rectangle2D>();

I suggest you use diamond inference:

List<Rectangle2D> rectangles = new ArrayList<>();

Advice 2

I also suggest you declare rectangles above as private final:

private final List<Rectangle2D> rectangles = new ArrayList<>();

Advice 3

List<Rectangle2D> rectanglesToDraw;

I would add private here too.

Advice 4

In findIntersections, you have:

ArrayList<Rectangle2D> intersections = new ArrayList<Rectangle2D>();

Better write this as

List<Rectangle2D> intersections = new ArrayList<>();

This adds up to maintainability of your code, say, if someone else wants to use a LinkedList instead.

Advice 5

surroundingRect can be written much shorter:

private Rectangle2D surroundingRect(List<Rectangle2D> rectangles) {

        Point topLeft = new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);
        Point bottomRight = new Point(Integer.MIN_VALUE, Integer.MIN_VALUE);

        for (Rectangle2D rect : rectangles) {
            topLeft.x = Math.min(topLeft.x, (int) rect.getMinX());
            topLeft.y = Math.min(topLeft.y, (int) rect.getMinY());
            bottomRight.x = Math.max(bottomRight.x, (int) rect.getMaxX());
            bottomRight.y = Math.max(bottomRight.y, (int) rect.getMaxY());
        }

        return new Rectangle2D.Double(topLeft.getX(), 
                                      topLeft.getY(), 
                                      bottomRight.getX() - topLeft.getX(),
                                      bottomRight.getY() - topLeft.getY());
    }

Advice 6

Rename Rectangles the JPanel to, say, RectangleViewPanel.

Advice 7

This is most important. I suggest you decouple GUI from the actual algorithm. You could come up with an abstract class/interface that defines the API for rectangle declutter algorithms, and derive from it for each actual algorithm. Your code may look like this (just an example):

AbstractRectangleDeclutter.java

import java.awt.Point;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.List;

public abstract class AbstractRectangleDeclutter {

    public abstract List<Rectangle2D> declutter(List<Rectangle2D> rectangles);

    protected List<Rectangle2D> copy(List<Rectangle2D> rectangles) { 
        List<Rectangle2D> newRectangles = new ArrayList<>(rectangles.size());

        for (Rectangle2D rectangle : rectangles) {
            Rectangle2D newRectangle = new Rectangle2D.Double();
            newRectangle.setRect(rectangle);
            newRectangles.add(newRectangle);
        }

        return newRectangles;
    }

    protected Rectangle2D 
        findSurroundingRectangle(List<Rectangle2D> rectangles) {
        Point topLeft = new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);
        Point bottomRight = new Point(Integer.MIN_VALUE, Integer.MIN_VALUE);

        for (Rectangle2D rect : rectangles) {
            topLeft.x = Math.min(topLeft.x, (int) rect.getMinX());
            topLeft.y = Math.min(topLeft.y, (int) rect.getMinY());
            bottomRight.x = Math.max(bottomRight.x, (int) rect.getMaxX());
            bottomRight.y = Math.max(bottomRight.y, (int) rect.getMaxY());
        }

        return new Rectangle2D.Double(topLeft.getX(), 
                                      topLeft.getY(), 
                                      bottomRight.getX() - topLeft.getX(),
                                      bottomRight.getY() - topLeft.getY());
    }

    protected List<Rectangle2D>
         findIntersectingRectangles(Rectangle2D rectangle,
                                    List<Rectangle2D> otherRectangles) {
        List<Rectangle2D> intersectingRectangles = new ArrayList<>();

        for (Rectangle2D otherRectangle : otherRectangles) {
            if (!rectangle.equals(otherRectangle) 
                    && rectangle.intersects(otherRectangle)) {
                intersectingRectangles.add(otherRectangle);
            }
        }

        return intersectingRectangles;
    }
}

DefaultRectangleDeclutter.java

import java.awt.Point;
import java.awt.geom.Rectangle2D;
import java.util.List;

public class DefaultRectangleDeclutter extends AbstractRectangleDeclutter {

    private static final int MOVEMENT_FACTOR = 10;

    private int numberOfIterations;

    @Override
    public List<Rectangle2D> declutter(List<Rectangle2D> inputRectangles) {
        numberOfIterations = 0;

        List<Rectangle2D> outputRectangles = copy(inputRectangles);
        Rectangle2D surroundingRectangle = 
               findSurroundingRectangle(inputRectangles);

        Point center = new Point((int) surroundingRectangle.getCenterX(),
                                 (int) surroundingRectangle.getCenterY());

        boolean hasIntersections;

        do {
            hasIntersections = false;

            for (Rectangle2D rectangle : outputRectangles) {
                List<Rectangle2D> intersectingRectangles = 
                        findIntersectingRectangles(rectangle, outputRectangles);

                if (!intersectingRectangles.isEmpty()) {
                    Point movementVector = new Point();
                    Point centerOfRectangle = 
                            new Point((int) rectangle.getCenterX(),
                                      (int) rectangle.getCenterY());

                    for (Rectangle2D intersectingRectangle 
                            : intersectingRectangles) {
                        Point centerOfIntersectingRectangle = 
                            new Point((int) intersectingRectangle.getCenterX(),
                                      (int) intersectingRectangle.getCenterY());

                        int xTranslation = 
                                (int)(centerOfRectangle.getX() - 
                                      centerOfIntersectingRectangle.getX());

                        int yTranslation =
                                (int)(centerOfRectangle.getY() - 
                                      centerOfIntersectingRectangle.getY());

                        movementVector.translate(
                                xTranslation < 0 ?
                                        -MOVEMENT_FACTOR :
                                         MOVEMENT_FACTOR,
                                yTranslation < 0 ?
                                        -MOVEMENT_FACTOR :
                                         MOVEMENT_FACTOR);
                    }

                    int xTranslation = (int)(centerOfRectangle.getX() -
                                             center.getX());

                    int yTranslation = (int)(centerOfRectangle.getY() -
                                             center.getY());

                    movementVector.translate(
                            xTranslation < 0 ? 
                                    -MOVEMENT_FACTOR :
                                     MOVEMENT_FACTOR,
                            yTranslation < 0 ?
                                    -MOVEMENT_FACTOR :
                                     MOVEMENT_FACTOR);

                    rectangle.setRect(
                        rectangle.getX() + movementVector.getX(),
                        rectangle.getY() + movementVector.getY(),
                        rectangle.getWidth(),
                        rectangle.getHeight());

                    hasIntersections = true;
                }
            }

            numberOfIterations++;
        } while (hasIntersections);

        return outputRectangles;
    }

    public int getNumberOfIterations() {
        return numberOfIterations;
    }
}

RectangleViewPanel.java

import java.awt.BasicStroke;
import java.awt.BorderLayout;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Rectangle2D;
import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.TimeUnit;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class RectangleViewPanel extends JPanel {

    private List<Rectangle2D> rectangleList;

    public List<Rectangle2D> getRectangleList() {
        return this.rectangleList;
    }

    public void setRectangleList(List<Rectangle2D> rectangleList) {
        this.rectangleList = rectangleList;
        repaint();
    }

    //Draws the rectangles in the frame from the rectanglesToDraw data structure  
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;

        if (rectangleList != null) {
            for (Rectangle2D entry : rectangleList) {
                g2d.setStroke(new BasicStroke(1));
                g2d.draw(entry);
            }
        }
    }

    //create GUI components and display it to the user
    protected static void createAndShowGUI() {
        RectangleViewPanel rects = new RectangleViewPanel();
        rects.setRectangleList(getRectangles());

        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) {
                AbstractRectangleDeclutter declutter = 
                        new DefaultRectangleDeclutter();

                long start = System.currentTimeMillis();
                List<Rectangle2D> newRectangles =
                        declutter.declutter(rects.getRectangleList());
                long end = System.currentTimeMillis();

                rects.setRectangleList(newRectangles);
                rects.repaint();

                System.out.println(
                        "That took "+ 
                                TimeUnit.MILLISECONDS
                                        .convert(end - start, 
                                                 TimeUnit.MILLISECONDS)
                                + " milliseconds.");
            }
        });

        JButton resetButton = new JButton("Reset");

        resetButton.addActionListener(new ActionListener() {

            @Override
            public void actionPerformed(ActionEvent e) {
                rects.setRectangleList(getRectangles());
                rects.repaint();
            }
        });

        buttonsPanel.add(fix);
        buttonsPanel.add(resetButton);

        frame.add(buttonsPanel, BorderLayout.SOUTH);

        frame.setSize(1920, 900);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {

            @Override
            public void run() {
                createAndShowGUI();
            }
        });
    }

    private static List<Rectangle2D> getRectangles() {
        List<Rectangle2D> rectangles = new ArrayList<>();

        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));
        rectangles.add(new Rectangle2D.Float(690, 229, 388, 114));
        rectangles.add(new Rectangle2D.Float(347, 341, 347, 425));
        rectangles.add(new Rectangle2D.Float(107, 515, 179, 158));
        rectangles.add(new Rectangle2D.Float(55, 487, 174, 153));
        rectangles.add(new Rectangle2D.Float(458, 553, 125, 128));
        rectangles.add(new Rectangle2D.Float(109, 566, 125, 128));
        rectangles.add(new Rectangle2D.Float(138, 166, 125, 128));

        int numRowsAndColumns = 20;

        // Add more rectangles
        for (int i = 0; i < numRowsAndColumns; i++) {
            for (int j = 0; j < numRowsAndColumns; j++) {
                rectangles.add(new Rectangle2D.Float(i * 20, j * 10, 25, 20));
            }
        }

        return rectangles;
    }
}

Bad advice 1

I guess greybeard knows better about computational geometry, yet, as a novice, I would do the next: sort all the rectangles by area. Then start laying them out from left to right to the top of the panel. When the first "row" is occupied, lay the next "row" from right to left, and so on.

Actually, I suspect that optimal layout minimizing the surrounding area is very hard to compute (NP-hard or something).

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ surroundingRect can be written much shorter come to think of it, iterated Rectangle2D.union() should do; even Rectangle2D union = rectangles.stream().skip(1).reduce(rectangles.get(0), (a, b) -> a.createUnion(b));. \$\endgroup\$ – greybeard Sep 26 '17 at 14:59
  • \$\begingroup\$ @greybeard Thanks. I will take a look at it. \$\endgroup\$ – coderodde Sep 26 '17 at 15:05
  • \$\begingroup\$ @greybeard Why do you skip(1)? \$\endgroup\$ – coderodde Sep 26 '17 at 15:51
  • \$\begingroup\$ While not strictly necessary, the skip(1) prevents "adding" rectangles.get(0) to itself. \$\endgroup\$ – greybeard Sep 26 '17 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy