I've been working on an algorithm to declutter rectangles. 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.

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.

Here is the code I'm working with (which is based heavily on this SO from another similar question: https://stackoverflow.com/a/3266158/33863)

public class Rectangles extends JPanel {
 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;
//
 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());
 }
 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 numIterations = 0;
 int movementFactor = 10; //ideally would be 1
 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;
 }
 }
 numIterations++;
 }
 System.out.println("That took " + numIterations+ " iterations.");
 Rectangles.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) {
 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();
 }
 });
 }
}

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