Java Partition Surface into Little Squares

Question

I would like to know if there is any algorithm that does something like this:

Given a specific surface it divides it into smaller rectangles of the same size.

Something like this example figure:

The grey area is the surface, and the red squares is the partition itself.

I am thinking if there is a optimized way to do this.

A very bad approach would be a for loop in all the pixels and check if there is a rectangle for that specific spot, if not, would create a rectangle, and so on..

Maybe someone knows a algorithm already done? or a better solution?

Thanks alot in advance ;)

Answer 1

Here's one way to go about it.

1. Create a mask of the image. (I just used Photoshop)

   

2. Steal AndrewThompson's code for Creating an Area from an Image and use it to create an Area of the image.

   Area imageArea = getOutline(Color.BLACK, imageMask);
   

3. Create a grid Rectangle2D objects for the entirety of the image.

   Rectangle2D[][] grid = new Rectangle2D[rows][cols];
   for (int i = 0; i < grid.length; i++) {
       int y = i * CELL_SIZE;
       for (int j = 0; j < grid[i].length; j++) {
           int x = j * CELL_SIZE;
           grid[i][j] = new Rectangle2D.Double(x, y, cellSize, cellSize);
       }
   }
   

4. Once you have the grid, you can just traverse the Rectangle2D objects and check if the Area.contains each individual Rectangle2D in the grid, and you can just add it to a List<Rectangle2D>. Only rectangles contained in the area will be added, giving you your final grid of rectangles to draw. In the example below, I just painted to rectangles as a visual.

   for (Rectangle2D[] rects : imageGrid) {
       for (Rectangle2D rect : rects) {
           if (imageArea.contains(rect)) {
               g2.drawRect((int) rect.getX(), (int) rect.getY(),
                       (int) rect.getWidth(), (int) rect.getHeight());
           }
       }
   }
   

---

Full example

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Area;
import java.awt.geom.GeneralPath;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class SquaresInArea extends JPanel {

    private static final int CELL_SIZE = 30;

    BufferedImage image;
    BufferedImage imageMask;
    Area imageArea;
    Rectangle2D[][] imageGrid;

    public SquaresInArea() {
        try {
            image = ImageIO.read(getClass().getResource("/resources/floorplan.png"));
            imageMask = ImageIO.read(getClass().getResource("/resources/floorplan-black.png"));
        } catch (IOException ex) {
            Logger.getLogger(SquaresInArea.class.getName()).log(Level.SEVERE, null, ex);
        }
        imageArea = getOutline(Color.BLACK, imageMask);
        imageGrid = createGrid();
    }

    private Rectangle2D[][] createGrid() {
        int width = image.getWidth();
        int height = image.getHeight();
        int rows = height / CELL_SIZE;
        int cols = width / CELL_SIZE;
        Rectangle2D[][] grid = new Rectangle2D[rows][cols];
        for (int i = 0; i < grid.length; i++) {
            int y = i * CELL_SIZE;
            for (int j = 0; j < grid[i].length; j++) {
                int x = j * CELL_SIZE;
                grid[i][j] = new Rectangle2D.Double(x, y, CELL_SIZE, CELL_SIZE);
            }
        }
        return grid;
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;
        g2.drawImage(image, 0, 0, this);
        g2.setColor(Color.YELLOW);
        g2.setStroke(new BasicStroke(3f));
        for (Rectangle2D[] rects : imageGrid) {
            for (Rectangle2D rect : rects) {
                if (imageArea.contains(rect)) {
                    g2.drawRect((int) rect.getX(), (int) rect.getY(),
                            (int) rect.getWidth(), (int) rect.getHeight());
                }
            }
        }
    }

    @Override
    public Dimension getPreferredSize() {
        return image == null ? new Dimension(300, 300)
                : new Dimension(image.getWidth(), image.getHeight());

    }

    private Area getOutline(Color target, BufferedImage bi) {
        // construct the GeneralPath
        GeneralPath gp = new GeneralPath();

        boolean cont = false;
        int targetRGB = target.getRGB();
        for (int xx = 0; xx < bi.getWidth(); xx++) {
            for (int yy = 0; yy < bi.getHeight(); yy++) {
                if (bi.getRGB(xx, yy) == targetRGB) {
                    if (cont) {
                        gp.lineTo(xx, yy);
                        gp.lineTo(xx, yy + 1);
                        gp.lineTo(xx + 1, yy + 1);
                        gp.lineTo(xx + 1, yy);
                        gp.lineTo(xx, yy);
                    } else {
                        gp.moveTo(xx, yy);
                    }
                    cont = true;
                } else {
                    cont = false;
                }
            }
            cont = false;
        }
        gp.closePath();

        // construct the Area from the GP & return it
        return new Area(gp);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                JFrame frame = new JFrame();
                frame.add(new SquaresInArea());
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }
}

here's another view for clarity

private final BasicStroke thin = new BasicStroke(1f);
private final BasicStroke thick = new BasicStroke(4f);

@Override
protected void paintComponent(Graphics g) {
    super.paintComponent(g);
    Graphics2D g2 = (Graphics2D) g;
    g2.drawImage(image, 0, 0, this);
    for (Rectangle2D[] rects : imageGrid) {
        for (Rectangle2D rect : rects) {
            if (imageArea.contains(rect)) {
                g2.setStroke(thick);
                g2.setColor(Color.GREEN);
                g2.draw(rect);
            } else {
                g2.setStroke(thin);
                g2.setColor(Color.RED);
                g2.draw(rect);
            }
        }
    }
}

Answer 2

Do you just want to fill it with squares - or do you want to fill it with the optimal number of squares?

An algorithm for the second is harder.

For the first just step through the image a square-size at a time. If the pixel at that point is filled then scan the full square, if it's all filled in then draw the square. If not then step to the next point.

i.e. if squares are 10*10 pixels:

for (int x=0;x<width;x+=SQUARE_SIZE) {
    for (int y=0;y<height;y+=SQUARE_SIZE) {
       // Now check if you can put a valid square here, if so draw it
    }
}