Basically, what I need to do is take a 2d array of bitflags and produce a list of 2d rectangles to fill the entire area with the minimum number of total shapes required to perfectly fill the space. I am doing this to convert a 2d top-down monochrome of a map into 2d rectangle shapes which perfectly represent the passed in image which will be used to generate a platform in a 3d world. I need to minimize the total number of shapes used, because each shape will represent a separate object, and flooding it with 1 unit sized squares for each pixel would be highly inefficient for that engine.
So far I have read in the image, processed it, and filled a two dimensional array of booleans which tells me if the pixel should be filled or unfilled, but I am unsure of the most efficient approach of continuing.
Here is what I have so far, as reference, if you aren't following:
public static void main(String[] args) {
File file = new File(args[0]);
BufferedImage bi = null;
try {
bi = ImageIO.read(file);
} catch (IOException ex) {
Logger.global.log(Level.SEVERE, null, ex);
}
if (bi != null) {
int[] rgb = bi.getRGB(0, 0, bi.getWidth(), bi.getHeight(), new int[bi.getWidth() * bi.getHeight()], 0, bi.getWidth());
Origin origin = new Origin(bi.getWidth() / 2, bi.getHeight() / 2);
boolean[][] flags = new boolean[bi.getWidth()][bi.getHeight()];
for (int y = 0; y < bi.getHeight(); y++) {
for (int x = 0; x < bi.getWidth(); x++) {
int index = y * bi.getWidth() + x;
int color = rgb[index];
int type = color == Color.WHITE.getRGB() ? 1 : (color == Color.RED.getRGB() ? 2 : 0);
if (type == 2) {
origin = new Origin(x, y);
}
flags[x][y] = type != 1;
}
}
List<Rectangle> list = new ArrayList();
//Fill list with rectangles
}
}
White represents no land. Black or Red represents land. The check for the red pixel marks the origin position of map, which was just for convenience and the rectangles will be offset by the origin position if it is found.
Edit: The processing script does not need to be fast, the produced list of rectangles will be dumped and that will be what will be imported and used later, so the processing of the image does not need to be particularly optimized, it doesn't make a difference.
I also just realized that expecting a 'perfect' solution is expecting too much, since this would qualify as a 'knapsack problem' of the multidimensionally constrained variety, if I am expecting exactly the fewest number of rectangles, so simply an algorithm that produces a minimal number of rectangles will suffice.
Here is a reference image for completion:
Edit 2: It doesn't look like this is such an easy thing to answer given no feedback yet, but I have started making progress, but I am sure I am missing something that would vastly reduce the number of rectangles. Here is the updated progress:
static int mapWidth;
static int mapHeight;
public static void main(String[] args) {
File file = new File(args[0]);
BufferedImage bi = null;
System.out.println("Reading image...");
try {
bi = ImageIO.read(file);
} catch (IOException ex) {
Logger.global.log(Level.SEVERE, null, ex);
}
if (bi != null) {
System.out.println("Complete!");
System.out.println("Interpreting image...");
mapWidth = bi.getWidth();
mapHeight = bi.getHeight();;
int[] rgb = bi.getRGB(0, 0, mapWidth, mapHeight, new int[mapWidth * mapHeight], 0, mapWidth);
Origin origin = new Origin(mapWidth / 2, mapHeight / 2);
boolean[][] flags = new boolean[mapWidth][mapHeight];
for (int y = 0; y < mapHeight; y++) {
for (int x = 0; x < mapWidth; x++) {
int index = y * mapWidth + x;
int color = rgb[index];
int type = color == Color.WHITE.getRGB() ? 1 : (color == Color.RED.getRGB() ? 2 : 0);
if (type == 2) {
origin = new Origin(x, y);
}
flags[x][y] = type != 1;
}
}
System.out.println("Complete!");
System.out.println("Processing...");
//Get Rectangles to fill space...
List<Rectangle> rectangles = getRectangles(flags, origin);
System.out.println("Complete!");
float rectangleCount = rectangles.size();
float totalCount = mapHeight * mapWidth;
System.out.println("Total units: " + (int)totalCount);
System.out.println("Total rectangles: " + (int)rectangleCount);
System.out.println("Rectangle reduction factor: " + ((1 - rectangleCount / totalCount) * 100.0) + "%");
System.out.println("Dumping data...");
try {
file = new File(file.getParentFile(), file.getName() + "_Rectangle_Data.txt");
if(file.exists()){
file.delete();
}
file.createNewFile();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file)));
for(Rectangle rect: rectangles){
bw.write(rect.x + "," + rect.y + "," + rect.width + ","+ rect.height + "\n");
}
bw.flush();
bw.close();
} catch (Exception ex) {
Logger.global.log(Level.SEVERE, null, ex);
}
System.out.println("Complete!");
}else{
System.out.println("Error!");
}
}
public static void clearRange(boolean[][] flags, int xOff, int yOff, int width, int height) {
for (int y = yOff; y < yOff + height; y++) {
for (int x = xOff; x < xOff + width; x++) {
flags[x][y] = false;
}
}
}
public static boolean checkIfFilled(boolean[][] flags, int xOff, int yOff, int width, int height) {
for (int y = yOff; y < yOff + height; y++) {
for (int x = xOff; x < xOff + width; x++) {
if (!flags[x][y]) {
return false;
}
}
}
return true;
}
public static List<Rectangle> getRectangles(boolean[][] flags, Origin origin) {
List<Rectangle> rectangles = new ArrayList();
for (int y = 0; y < mapHeight; y++) {
for (int x = 0; x < mapWidth; x++) {
if (flags[x][y]) {
int maxWidth = 1;
int maxHeight = 1;
Loop:
//The search size limited to 400x400 so it will complete some time this century.
for (int w = Math.min(400, mapWidth - x); w > 1; w--) {
for (int h = Math.min(400, mapHeight - y); h > 1; h--) {
if (w * h > maxWidth * maxHeight) {
if (checkIfFilled(flags, x, y, w, h)) {
maxWidth = w;
maxHeight = h;
break Loop;
}
}
}
}
//Search also in the opposite direction
Loop:
for (int h = Math.min(400, mapHeight - y); h > 1; h--) {
for (int w = Math.min(400, mapWidth - x); w > 1; w--) {
if (w * h > maxWidth * maxHeight) {
if (checkIfFilled(flags, x, y, w, h)) {
maxWidth = w;
maxHeight = h;
break Loop;
}
}
}
}
rectangles.add(new Rectangle(x - origin.x, y - origin.y, maxWidth, maxHeight));
clearRange(flags, x, y, maxWidth, maxHeight);
}
}
}
return rectangles;
}
My current code's search for larger rectangles is limited to 400x400 to speed up testing, and outputs 17,979 rectangles, which is a 99.9058% total reduction of rectangles if I treated each pixel as a 1x1 square(19,095,720 pixels). So far so good.
